本文迁移自洛谷原文。
link
题目大意：
给出一个长度为 的序列和 个询问。对于每个询问，输入 ，输出满足 的 的对数。
题解：
考虑我们固定一个起点 ，从 到 扩张区间的右端点 ，考虑区间 gcd 的变化。
显然，这个 gcd 最多只会变化 次（ 是值域），因为每次变化必然是砍掉一个（或一些）质因数，而质因数的个数是 级别的。
所以我们可以考虑枚举开头，每次二分出下一个变化点的位置，每个开头二分 次，就可以求出所有可能的 gcd 的值并得到出现次数了。
注意用 表预处理一下 gcd，复杂度就可以做到 了。
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mxn=1e6+6;
int st[mxn][20],n,q,a[mxn],lg[mxn];
inline int ask(int l,int r){
int t=lg[r-l+1];
return __gcd(st[l][t],st[r-(1<<t)+1][t]);
}
map<int,ll>cnt;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;++i)cin>>a[i],st[i][0]=a[i];
for(int i=2;i<=n;++i)lg[i]=lg[i>>1]+1;
for(int j=1;j<20;++j)for(int i=1;i<=n;++i)st[i][j]=__gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]);
for(int i=1;i<=n;++i){
int cur=i,val=a[i];
while(1){
int lo=cur,hi=n+1,md;
for(;lo<hi-1;){
md=lo+hi>>1;
if(ask(i,md)!=val)hi=md;
else lo=md;
}
cnt[val]+=hi-cur;
cur=hi;val=ask(i,hi);
if(hi==n+1)break;
}
}
for(;q--;){
int x;cin>>x;
cout<<cnt[x]<<'\n';
}
}
|