[Codeforces475D]CGCDSSQ（数学相关+二分）

=== ===

这里放传送门

=== ===

题解

最关键的一点就是注意到如果固定左端点然后右端点从左往右移动，区间gcd最多只会变化 logV 次。因为首先gcd是单调不上升的，每次变化它肯定是要变小；变小的同时还得保证它是左端点位置那个数字 x[l] 的因数，所以每次最少只能去掉 x[l] 的一个质因数，也就是它最少要缩小两倍。

那么也就是说固定一个左端点的时候右边最多只有 log 级别的gcd区间，那么就可以枚举左端点然后二分gcd变化的地方把所有区间都预处理出来，答案存在map里就可以直接回答询问了。

代码

#include<map> #include<cstdio> #include<cstring> #include<algorithm> #define Pow 18 using namespace std; int n,val[100010],st[100010][20],q,r[300010],lg2[100010]; map<int,long long> ans; int gcd(int a,int b){ if (a==0||b==0) return 0; int r=a%b; while (r!=0){ a=b;b=r;r=a%b; } return b; } void get_st(){ for (int i=1,p=0;i<=n;i++){ while ((1<<p)<=i) ++p; lg2[i]=p-1; } for (int i=1;i<=n;i++) st[i][0]=val[i]; for (int j=1;j<=Pow;j++) for (int i=1;i<=n;i++) if (i+(1<<(j-1))<=n) st[i][j]=gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]); } int get_gcd(int l,int r){ int j=lg2[r-l+1],tmp; tmp=r-(1<<j)+1; return gcd(st[l][j],st[tmp][j]); } int divide(int l,int r,int S,int x){ int mid,v,ans=n+1; while (l<=r){ mid=(l+r)>>1; v=get_gcd(S,mid); if (v<=x){ ans=min(ans,mid);r=mid-1; }else l=mid+1; } return ans; } void work(int s){ int g=val[s],last,ptr,v; last=ptr=s; while (ptr<=n){ ptr=divide(s,n,s,g-1); ans[g]+=(long long)(ptr-last);//累加当前gcd下的答案 last=ptr;g=get_gcd(s,ptr);//指针后移 } } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&val[i]); get_st(); for (int i=1;i<=n;i++) work(i); scanf("%d",&q); for (int i=1;i<=q;i++){ int x;scanf("%d",&x); printf("%I64d\n",ans[x]); } return 0; }