Problem
给你一个长为 \(N(1\leq N \leq 1\times 10^5)\) 的整数序列：\(a_{1},\cdots,a_{n}(0 <a_{i} \leq 1\times 10^9)\)。
有 \(Q (1\leq Q \leq 1\times 10^5)\) 次提问。每次提问有个范围 \(l, r\)，你需要计算出 \(\gcd(a_{l},,a_{l+1},...,a_{r})\) ，并且统计数对 \((l’, r’) \boxed{{(1 \leq l' < r' \leq N)}}\) 的数量。数对满足 \(\gcd(a_{l’},a_{l’+1},...,a_{r’})\) 等于 \(\gcd(a_{l},a_{l+1},...,a_{r})\).
（\(l'=r'\) 似乎是可以的，不知道什么鬼）
Solution
考虑第一问。非常简单，线段树或者 ST 表，因为 \(\gcd\) 有结合律，又有 \(\gcd(x,x)=x\)。
考虑第二问，这一问显然可以暴力预处理答案，但是怎么暴力。考虑枚举右端点，动态维护一个左端点的队列表示可能的 \(\gcd\)，那么我们每次放入 \(a_r\)，然后把队列中的每个数和 \(a_r\) 取个 \(\gcd\)。这样我们就知道了这个序列的所有 \(\gcd\)，形式化一点可以是这样：
\[S_i=\{a_i\}\cup\{\gcd(x,a_i)|x\in S_{i-1}\}. \]但是为什么它对啊，考虑分析一下 \(S_i\)，我们发现随着数字一个个被加进去（固定 \(r\) 向左移动 \(l\)），\(\gcd\) 要么不变要么至少除以二，所以最多被除 \(\log\) 次，所以 \(S_i\) 在去重后的大小不超过 \(\log V\)。
这样的方法也可以查询区间 \(\gcd\)，暴力遍历 \(S_r\)，根据定义找到答案。写的时候建议倒着。
Solution'
但是有些同学读题不认真，读成 统计数对 \((l’, r’) \boxed{{(l \leq l' \leq r' \leq r)}}\)，非常悲伤，但还能做。首先离线询问。
枚举要找的 \(d\)，变成询问区间 \([L,R]\) 中有多少个区间的 \(\gcd=d\)，非常简单，我们扫描线，大概就是对于形如 \((l,[r])\) 的 pair（表示 \([l,r'\in[r]]\) 的 \(\gcd=d\)），只保留所有 \(l\geq L\) 的，将所有 \([r]\) 的位置加一，然后查询 \([L,R]\) 的和就是了。那么这非常的正确。\(O(n\log^2 n)\)。
Code
原题
#include <map>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
typedef pair<int,int> pii;
int gcd(int x,int y){return !y?x:gcd(y,x%y);}
int n,Q,a[1<<17];
map<int,LL> buc;
vector<pii> d[1<<17];
int mian(){
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=n;i>=1;i--){
d[i].push_back(pii{i,a[i]});
if(i<n) for(pii e:d[i+1]){
pii t={e.first,gcd(e.second,a[i])};
if(t.second==d[i].back().second) d[i].back().first=t.first;
else d[i].push_back(t);
}
int last=i-1;
for(pii e:d[i]) buc[e.second]+=e.first-last,last=e.first;
}
scanf("%d",&Q);
for(int l,r;Q--;){
scanf("%d%d",&l,&r);
for(pii e:d[l]) if(r<=e.first){
printf("%d %lld\n",e.second,buc[e.second]);
break;
}
}
return 0;
}
void reset(){
static int cnt=0; printf("Case #%d:\n",++cnt);
buc=map<int,LL>();
for(int i=1;i<=n;i++) d[i].clear();
}
int main(){
// #ifdef LOCAL
// freopen("input.in","r",stdin);
// #endif
for(scanf("%*d");~scanf("%d",&n);reset(),mian());
return 0;
}
加强
#include <map>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cassert>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
typedef pair<int,int> pii;
template<int N,class T=int> struct fenwick{
T t[N+10];
fenwick(){memset(t,0,sizeof t);}
void add(T k,int p){for(;p<=N;p+=p&-p) t[p]+=k;}
T query(int p){T res=0;for(;p>=1;p-=p&-p) res+=t[p];return res;}
};
template<int N,class T=int> struct segtree{//exfenwick
fenwick<N,T> s,t;
void add(T k,int l,int r){s.add(k,l),s.add(-k,r+1),t.add(k*(l-1),l),t.add(-k*r,r+1);}
T query(int p){return s.query(p)*p-t.query(p);}
T query(int l,int r){return query(r)-query(l-1);}
};
int gcd(int x,int y){return !y?x:gcd(y,x%y);}
int n,Q,a[1<<17],Lq[1<<17],Rq[1<<17];
map<int,vector<int>> ids;
map<int,vector<tuple<int,int,int>>> idd;
vector<pii> d[1<<17];
LL ans[1<<17];
segtree<1<<17,LL> t;
int solve(int l,int r){
for(pii e:d[l]) if(r<=e.first) return e.second;
assert(0); return -1;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=n;i>=1;i--){
d[i].push_back(pii{i,a[i]});
if(i<n) for(auto&&e:d[i+1]){
pii t={e.first,gcd(e.second,a[i])};
if(t.second==d[i].back().second) d[i].back().first=t.first;
else d[i].push_back(t);
}
int last=i-1;
for(auto&&e:d[i]) idd[e.second].emplace_back(i,last+1,e.first),last=e.first;
}
scanf("%d",&Q);
for(int i=1;i<=Q;i++) scanf("%d%d",&Lq[i],&Rq[i]),ids[solve(Lq[i],Rq[i])].push_back(i);
for(auto&&elem:ids){
int d=elem.first;
vector<int>&&id=move(elem.second);
auto&&ds=move(idd[d]);
for(auto&&rng:ds) t.add(1,get<1>(rng),get<2>(rng));
int now=(int)ds.size()-1;
sort(id.begin(),id.end(),[&](int i,int j){return Lq[i]<Lq[j];});
for(int i:id){
while(now>=0&&get<0>(ds[now])<Lq[i]) t.add(-1,get<1>(ds[now]),get<2>(ds[now])),now--;
ans[i]=t.query(Lq[i],Rq[i]);
}
while(now>=0) t.add(-1,get<1>(ds[now]),get<2>(ds[now])),now--;
}
for(int i=1;i<=Q;i++) printf("%d %d\n",solve(Lq[i],Rq[i]),ans[i]);
return 0;
}