题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=5726
给一个数组a，大小为n，接下来有m个询问，每次询问给出l、r，定义f[l,r]=gcd（al，al+1，...，ar），问f[l,r]的值 和 有多少对（l'，r'）使得f[l',r']=f[l,r]。n<=1e5，m<=1e5，1<=l<=r<=n，1<=l'<=r'。
1.线段树法+思维：
线段树的每个节点存区间gcd，query查询即可
为了统计区间gcd为k的区间个数（k=f[l,r]），需要先预处理
参考网上的博客，两种预处理的方法：
（1）和query函数类似，递归搜索（不过这个方法我 看了半天也不是特别懂）
（2）暴力预处理，巧用map（推荐！orz）
2.st表法+思维：
https://www.cnblogs.com/hchlqlz-oj-mrj/p/5687347.html
暴力预处理：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 1000000007; const int maxn=1e5+10; int g[maxn*4],a[maxn]; map<int,ll> ans;//存最终答案 map<int,ll> p[maxn];//p[i]表示以i结尾的gcd的区间集合,前者为gcd，后者为对应的区间个数 int t, n, q, x, y; int Gcd(int a,int b) { return b == 0 ? a : Gcd(b, a % b); } void update(int id) { g[id] = Gcd(g[id << 1], g[id << 1 | 1]); } void build(int l,int r,int id) { if(l == r) { g[id] = a[l]; return ; } int mid = (l + r) >> 1; build(l, mid, id << 1); build(mid + 1, r, id << 1 | 1); update(id); } int query(int l, int r, int x, int y, int id) { if(x <= l && r <= y) return g[id]; int mid = (l + r) >> 1; int le=0,ri=0; if(x <= mid) le = query(l, mid, x, y, id << 1); if(y > mid) ri = query(mid + 1, r, x, y, id << 1 | 1); if(!le) swap(le, ri);//le为0， 不能求ri%0 return Gcd(le, ri);//Gcd(x, 0) = x } int main() { //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin); scanf("%d", &t); int Case = 1; while(t--) { printf("Case #%d:\n", Case++); scanf("%d", &n); ans.clear();//清空!! for(int i = 1; i <= n; i++) p[i].clear(); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); build(1, n, 1); ans[a[1]] = 1,p[1][a[1]] = 1; for(int i = 2; i <= n; i ++) { ans[a[i]]++, p[i][a[i]] += 1; for(map<int,ll>::iterator it = p[i-1].begin(); it != p[i-1].end(); it++) { int tmp = Gcd(a[i], it->first);//求a[i]和之前的数的gcd p[i][tmp] += it->second; ans[tmp] += it->second; } } scanf("%d",&q); while(q--) { scanf("%d %d", &x, &y); int k = query(1, n, x, y, 1); printf("%d %lld\n",k, ans[k]); } } return 0; }
递归搜索预处理：(可跳过)
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 1000000007; const int maxn=1e5+10; int g[maxn*4],a[maxn]; map<int,ll> ans; int t, n, q, x, y; int Gcd(int a,int b) { return b == 0 ? a : Gcd(b, a % b); } void update(int id) { g[id] = Gcd(g[id << 1], g[id << 1 | 1]); } void build(int l,int r,int id) { if(l == r) { g[id] = a[l]; return ; } int mid = (l + r) >> 1; build(l, mid, id << 1); build(mid + 1, r, id << 1 | 1); update(id); } int query(int l, int r, int x, int y, int id) { if(x <= l && r <= y) return g[id]; int mid = (l + r) >> 1; int le=0,ri=0; if(x <= mid) le = query(l, mid, x, y, id << 1); if(y > mid) ri = query(mid + 1, r, x, y, id << 1 | 1); if(!le) swap(le, ri);//le为0， 不能求ri%0 return Gcd(le, ri);//Gcd(x, 0) = x } int search(int l, int r, int x, int y, int cur, int id, int &GCD) { if(x <= l && r <= y) { if(Gcd(g[id], GCD) < cur) { if(l == r) return l; else { int mid = (l + r) >> 1, le = 0, ri = 0; le = search(l, mid, x, y, cur, id << 1, GCD); if(le) return le; ri = search(mid + 1, r, x, y, cur, id << 1 | 1, GCD); return ri; } } else { GCD = Gcd(g[id], GCD); return 0; } } int mid = (l + r) >> 1, le = 0, ri = 0; if(x <= mid) le = search(l, mid, x, y, cur, id << 1, GCD); if(le) return le; if(y > mid) ri = search(mid + 1, r, x, y, cur, id << 1 | 1, GCD); return ri; } int main() { //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin); scanf("%d", &t); int Case = 1; while(t--) { ans.clear();//清空!! printf("Case #%d:\n", Case++); scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); build(1, n, 1); int GCD, nex; for(int i = 1; i <= n; i++) { int G=query(1, n, i, n, 1); //cout << "g :" << G<<endl; for( int now = i, cur = a[i]; now <= n; ) { if(G == cur) { ans[G] += n - now + 1; break; } GCD = a[i]; nex = search(1, n, i, n, cur, 1, GCD);//nex 表示【i，i+1】，【i，i+2】，。。【i，nex-1】内的gcd都是cur ans[cur] += nex - now; //cout<< " nex - now:"<<nex - now << endl; now = nex; cur = Gcd(a[now], cur); } } scanf("%d",&q); while(q--) { scanf("%d %d", &x, &y); int k = query(1, n, x, y, 1); printf("%d %lld\n",k, ans[k]); } } return 0; }【参考博客】：
https://blog.csdn.net/qq_40507857/article/details/81675524
https://blog.csdn.net/u013167299/article/details/51979844
