牛客小白月赛81 F 小辰刚学gcd

LInk
首先我们可以注意到,两个数的gcd要不是它们当中较小的那一个要不是它本身。
所以对于一个特定的 \(r\),\(gcd_{i=p}^r,1<=p<=r\)来说，答案不会超过32种。
并且因为gcd的性质，答案一定是成块且递减的。
所以我们可以直接记录下对于每一个\(r\),答案都有哪些，从哪里开始出现。
并且\(r+1\)的值可以从\(r\)推出。
最后只要对于所有可能的答案进行判断就可以了。
\(O(32n)\)的时间复杂度

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
int n,m;
int ans[600005][33];
int v[600005][33];
int a[600005];
int l,r;
map<int,int> mp; 
int gcd(int x,int y){
    return y==0?x:gcd(y,x%y);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;++i){
        ans[i][0]++;
        ans[i][1]=i;
        v[i][1]=a[i];
        mp[a[i]]=i;
        for(int j=1;j<=ans[i-1][0];++j){
            int vv=gcd(a[i],v[i-1][j]);
            if(!mp.count(vv)||mp[vv]!=i){
                mp[vv]=i;
                ans[i][0]++;
                ans[i][ans[i][0]]=ans[i-1][j];
                v[i][ans[i][0]]=vv;
            }
        }
    }
    while(m--){
        scanf("%d%d",&l,&r);
        int cnt=1;
        int cntt=0;
        while(cnt<=ans[r][0]){
            if(l<=ans[r][cnt]){
            cntt++;
            }
            cnt++;
        }
        printf("%d\n",cntt);
    }
    return 0;
}