【HDU 5726】GCD

题目戳这里

题目描述

Give you a sequence ofN(N≤100,000)integers :a1,...,an(0<ai≤1000,000,000). There areQ(Q≤100,000)queries. For each queryl,ryou have to calculategcd(al,,al+1,...,ar)and count the number of pairs(l′,r′)(1≤l<r≤N)such thatgcd(al′,al′+1,...,ar′)equalgcd(al,al+1,...,ar).

解题思路

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
int t,n,q;
int a[100050],st[100050][25];
int loooog[100050];
map<int,long long>ans;
inline void read(int &x){
    x=0; register char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
}
inline int gcd(int x,int y){
    return x==0?y:gcd(y%x,x);
}
inline int query(int x,int y){
    int z=loooog[y-x+1];
    return gcd(st[x][z],st[y-(1<<z)+1][z]);
}
inline void solve(int x,int y){
    int temp=query(x,y);
    printf("%d ",temp);
    printf("%lld\n",ans[temp]);
}
int main(){
    loooog[0]=-1;
    for(register int i=1;i<=100000;i++)loooog[i]=loooog[i>>1]+1;
    read(t);
    for(register int fuck=1;fuck<=t;fuck++){
        read(n);
        memset(st,0,sizeof(st));
        ans.clear();
        for(register int i=1;i<=n;i++){
            read(a[i]);
            st[i][0]=a[i];
        }
        read(q);
        printf("Case #%d:\n",fuck);
        int N=loooog[n]+1;
        for(register int i=1;i<=N;i++){
            for(register int j=1;j<=n-(1<<i)+1;j++){
                st[j][i]=gcd(st[j][i-1],st[j+(1<<(i-1))][i-1]);
            }
        }
        for(register int i=1;i<=n;i++){
            register int now=i,temp=a[i];
            for(;now<=n;){
                int l=now,r=n;
                while(l<r){
                    int m=(l+r+1)>>1;
                    if(query(i,m)==temp)l=m;
                    else r=m-1;
                }
                if(ans[temp])ans[temp]+=(l-now+1);
                else ans[temp]=(l-now+1);
                now=l+1,temp=gcd(temp,a[l+1]);
            }
        }
        register int l,r;
        for(register int i=1;i<=q;i++){
            read(l),read(r);
            solve(l,r);
        }
    }
}