题面
给定 (n) 和 (a_i(1le ile n))，(m) 和 (b_j(1le jle m))，求对于每个 (j)，(a_i) 区间 (gcd) 为 (b_j) 的区间数。
数据范围：(1le nle 4cdot 10^6)，(1le mle 2cdot 10^5)，(1le a_i,b_ile 4cdot 10^4)。
解法
唠叨
蒟蒻考场上 (Theta(n{ m d}(a))) 的公约数容斥过了……赛后 ( t MLE#13)。
正解有好多种，都是 (Theta(nlog^2n+m)) 的，其中一个 (log) 来自 (gcd)。蒟蒻说说最妙的一种。
奇妙的正解
(f_{i,j}) 表示右端点为 (i)，(gcd) 为 (j) 的区间数。
[f_{i,gcd(a_i,j)}=sum f_{i-1,j}
]
当然要考虑区间 ([i,i])，(f_{i,a_i}++)。
然后 (i) 这维滚动掉，(j) 这维用哈希表。
时间复杂度 (Theta(nlog^2n+m))。
- 证明：
只考虑 (f_{i,j}>0) 的 (j)，如果有 (cnt) 种，如果要加 (1) 种不减少原来的 (cnt) 种，必须是原来 (cnt) 种的公倍数。所以任何时候，(cnt) 必然是 (log) 级别的。
然后 (ans_j=sum_{i=1}^n f_{i,j})，可以求 (f) 的时候一起求，每次查询 (Theta(1))。
代码
#include <bits/stdc++.h>
using namespace std;
//Start
typedef long long ll;
typedef double db;
#define mp(a,b) make_pair(a,b)
#define x first
#define y second
#define be(a) a.begin()
#define en(a) a.end()
#define sz(a) int((a).size())
#define pb(a) push_back(a)
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
//Data
const int N=4e6,A=4e4;
int n,m; ll ans[A+1];
unordered_map<int,ll> hsh[2];
int gcd(int x,int y){return x?gcd(y%x,x):y;}
//Main
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
int now=1,a;
while(n--){
cin>>a,now^=1,hsh[now].clear();
for(auto it:hsh[now^1]){
int g=gcd(a,it.x);
hsh[now][g]+=it.y,ans[g]+=it.y;
}
hsh[now][a]++,ans[a]++;
}
cin>>m;
int b;
while(m--){
cin>>b;
cout<<ans[b]<<'
';
}
return 0;
}
祝大家学习愉快！