题目链接:点击这里
题意:每次询问一个区间的gcd,和这个gcd相同的区间的个数。
区间的gcd个数最多不会超过 log(max) 个, 而且gcd序列又是递减的,所以直接暴力枚举左端点,对右端点二分求出每一个值的区间扔到map里面统计一下就好了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <map>
using namespace std;
#define maxn 100005
#define mod 1000000007
int dp[maxn][];
int a[maxn];
int n, q;
map <int, long long> gg;
int scan () {
char ch=' ';
while(ch<'0'||ch>'9')ch=getchar();
int x=;
while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
return x;
}
void rmq_init () {
for (int i = ; i < n; i++) dp[i][] = a[i];
for (int j = ; (<<j) <= n; j++) {
for (int i = ; i+(<<j)- < n; i++) {
dp[i][j] = __gcd (dp[i][j-], dp[i+(<<(j-))][j-]);
}
}
}
int rmq (int l, int r) {
int k = ;
while ((<<(k+)) <= r-l+) k++;
return __gcd (dp[l][k], dp[r-(<<k)+][k]);
}
void solve () {
for (int i = ; i < n; i++) {
int pos = n-;
while (pos >= i) {
int tmp = rmq (i, pos);
int l = i, r = pos;
while (r-l > ) {
int mid = (l+r)>>;
if (rmq (i, mid) == tmp) r = mid;
else l = mid;
}
int cur;
if (rmq (i, l) == tmp) cur = l;
else cur = r;
gg[tmp] += (pos-cur+);
pos = cur-;
}
}
}
int main () {
int t, kase = ;
scanf ("%d", &t);
while (t--) {
printf ("Case #%d:\n", ++kase);
gg.clear ();
n = scan ();
for (int i = ; i < n; i++) a[i] = scan ();
rmq_init ();
solve ();
q = scan ();
while (q--) {
int l = scan (), r = scan ();
int ans = rmq (l-1, r-1);
printf ("%d %lld\n", ans, gg[ans]);
}
}
return ;
}