我们固定左端点 每当右边加入一个数 那么gcd肯定在原来的基础上丢掉某几个质因数
由于一个数最多有log个质因子 所以对于一个l gcd(l,r)不同的区间最多有log个
于是我们枚举左端点 二分寻找右端点 用线段树/st表查询一个区间里的gcd 再用哈希表更新
但是只能拿80分
区间是可合并的 用链表来维护每个数的下一个不同的分界点 然后每次加 后合并相同的区间
#include<bits/stdc++.h> #include<tr1/unordered_map> #define N 500005 #define ll long long using namespace std; using namespace tr1; template<class T> inline void read(T &x) { x=0; static char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } int n,q,a[N],next[N]; unordered_map<int,ll> m; int main() { read(n); read(q); for(int i=1;i<=n;i++) read(a[i]),next[i]=i+1; for(int i=n;i>=1;i--) { int pre=i; for(int j=i;j<=n;j=next[j]) { a[j]=__gcd(a[j],a[pre]); if(a[j]==a[pre]) next[pre]=next[j]; m[a[j]]+=(next[j]-j); pre=j; } } while(q--) { ll x; read(x); cout<<m[x]<<" "; } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9844882.html
相关资源：各显卡算力对照表！