CF 475D CGCDSSQ 枚举,思维+gcd

题意:给出长度为n的序列a,Q次询问:第i次询问x[i]:有多少个区间[l,r]的gcd为x[i]? n<=1e5,q<=3e5,a[i],x[i]<=1e9. 以a[i]开头的区间 随着区间长度增加 gcd是非递增的(套路阿.) 每次至少缩小一半 所以分界点不会超过loga[i]个. 关键如何快速找到这些端点. 可以用st表预处理出[l,r]的gcd值 二分最早变化的端点 O(n*log^3n) TLE. map(i+1)存左端点为i+1时 gcd为x时,的区间个数

当左端点为i时,用map[i+1]来更新map(i)即可.

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+5; int n,a[N]; int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } map<int,ll>res,now,nxt; void work() { map<int,ll>::iterator it; for(int i=n;i>=1;i--) { now.clear(); now[a[i]]++; for(it=nxt.begin();it!=nxt.end();it++) { int d=gcd(a[i],it->first); now[d]+=it->second; } for(it=now.begin();it!=now.end();it++) res[it->first]+=it->second; swap(now,nxt); } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); work(); int Q,x; scanf("%d",&Q); while(Q--) { scanf("%d",&x); printf("%I64d\n",res[x]); } return 0; }