牛客小白月赛81 F题解

2023/11/17 算法竞赛 题解 C++ 牛客 gcd 小白月赛 思维

想了半个多小时才发现原来和之前Codeforces div3的最后一题是一个题，于是写一遍加深印象

题面

给一个长度为 n 的数组 ai(i=1,2,⋯,n)

对数组进行多次查询，每次查询数组的一个连续区间 [l,r] ，需要计算集合 的大小

解

一开始以为是预处理，想了很久不知道怎么搞，想过st表，线段树，但感觉都做不了

突然发现后缀的 gcd  收敛的很快，非常快收敛到1之后就不用计算了，因为只用求不同的后缀gcd的个数，并且这样的后缀gcd是单调不增的

然后想到后缀gcd可能收敛的特别快，以至于可以改变复杂度

想了一下发现是log的速度，设目前的后缀gcd为 ，如果 ai − 1 对gcd有贡献，那么 ai − 1 分解成质因数幂的形式之后一定比后缀gcd的质因数幂中某一项的指数更小，那么有贡献的 ai 的数量级是 O(maxjαj) = O(log(ai))

于是暴力就是对的

但是需要注意一下没有贡献的 ai ，如果 ai − 1 没有贡献，那么满足 ai ∣ ai − 1 ，如果 ai − 1 一直比 ai 大，那么这样的 ai − 1 不会很多（指数增长），但是相等的可能会很多。

而相等的一串是可以直接跳过去的，采用静态链表跳转，保证了复杂度是 O(mlog(∑i(ai))) 级别的，可以过

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
typedef unsigned long long ull;
#define dmp(x) cerr<<"DEBUG"<<__LINE__<<":"<<#x<<" "<<x<<endl
const ll INF=0x3f3f3f3f3f3f3f3fLL;
typedef pair<int,int> pii;
const int N=6e5+5;
int a[N],lt[N];
signed main() {
    ios::sync_with_stdio(false);cin.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
        lt[i]=i-1;
    for(int i=1;i<=n;i++){
        if(a[i-1]%a[i]==0)
            lt[i]=lt[i-1];
    }
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        int ans=1,now=a[r];
        for(int j=r;j>=l;j=lt[j]){
            int tmp=__gcd(now,a[j]);
            if(tmp!=now)
                ans++;
            now=tmp;
            if(now==1)
                break;
        }
        cout<<ans<<'\n';
    }
    return 0;
}
img_show