给n个数， 定义一个运算f[l,r] = gcd(al, al+1,....ar)。 然后给你m个询问， 每次询问给出l, r。 求出f[l, r]的值以及有多少对l', r' 使得f[l, r] = f[l', r']。
第一个很简单， 用倍增的思想就可以了。
然后是第二个， 我们枚举每一个左端点i， 显然f[i, j]是只降不增的。 那么我们可以二分找到所有使得f[i, j]下降的值j。 因为gcd每次至少变为原来的二分之一， 而ai最大为1e9. 所以最多只有log2(1e9)个这样的点。 我们都找出来然后放到map里就可以了。 具体看代码
#include <bits/stdc++.h> using namespace std;
#define ll long longint n;
const int maxn = 1e5+;
int a[maxn], f[maxn][], mm[maxn];
map <int, ll> mp;
int gcd(int a, int b)
{
return b?gcd(b, a%b):a;
}
void initrmq()
{
mm[] = -;
for(int i = ; i <= n; i++) {
mm[i] = ((i&(i-))==)?mm[i-]+:mm[i-];
}
for(int j = ; j < ; j++) {
for(int i = ; i + (<<j)- <= n; i++) {
f[i][j] = gcd(f[i][j-], f[i+(<<(j-))][j-]);
}
}
}
int query(int l, int r)
{
int k = mm[r-l+];
return gcd(f[l][k], f[r-(<<k)+][k]);
}
void pre()
{
for(int i = ; i <= n; i++) {
int g = f[i][];
int L = i, tmp;
while(L <= n) {
int l = L, r = n;
while(l <= r) {
int mid = l+r>>;
if(query(i, mid) == g) {
tmp = mid;
l = mid+;
} else {
r = mid-;
}
}
mp[g] += (tmp-L+);
L = tmp+;
g = gcd(g, f[L][]);
}
}
}
int main()
{
int t, m, l, r;
cin>>t;
for(int casee = ; casee <= t; casee++) {
cin>>n;
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
f[i][] = a[i];
}
mp.clear();
initrmq();
pre();
cin>>m;
printf("Case #%d:\n", casee);
for(int i = ; i < m; i++) {
scanf("%d%d", &l, &r);
int ans = query(l, r);
printf("%d %lld\n", ans, mp[ans]);
}
}
}