【HDU5726】GCD（区间GCD查询+统计区间gcd为k的区间个数----线段树/st表+思维）
题目地址：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
ac代码（线段树法）：
暴力预处理：
#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;
}
【参考博客】：
