思路：ST表+二分
代码：
#include<cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <map>
typedef long long LL;
using namespace std;
const int maxn = 134536;
int arr[maxn] = {}, book[20][maxn] = {};
int gcd(int xx, int yy)
{
return xx % yy == 0 ? yy : gcd(yy, xx % yy);
}
int query(int ll, int rr)
{
//printf(“query\n”);
//printf(“%d %d\n”, ll, rr);
int kk = (int)(log2((double)(rr – ll + 1)));
//printf(“%d %d\n”, kk, rr – (1 << kk) + 1);
return gcd(book[kk][ll], book[kk][rr – (1 << kk) + 1]);
}
void rmq(int n)
{
for(int i = 1; i <= n; i++)
{
book[0][i] = arr[i];
///先记录下这串数字的本身作为公因数
}
for(int i = 1; (1 << i) <= n; i++)
{
for(int j = 1; j + (1 << i) – 1 <= n;j++)
{
book[i][j] = gcd(book[i – 1][j], book[i – 1][j + (1 << i – 1)]);
///printf(“%d %d %d\n”, i, j, book[i][j]);
}
}
}
map<int, long long>maps;
void sets(int n)
{
rmq(n);
maps.clear();
for(int i = 1; i <= n; i++)
{
int j = i, gg = book[0][i];
while(j <= n)
{
int ll = j, rr = n;
while(ll < rr)
{
int mid = (ll + rr + 1) >> 1;
///printf(“lr : %d %d %d\n”, ll, rr, mid);
///printf(“%d\n”, query(j, mid));
if(query(j, mid) == gg)
{
ll = mid;
}
else rr = mid – 1;
}
maps[gg] += (ll – j + 1);
//printf(“i j ll gg maps\n”);
//printf(“%d %d %d %d %lld\n”, i, j, ll, gg, maps[gg]);
j = ll + 1;
if(j <= n) gg = query(i, j);
}
}
}
int main()
{
int _;
scanf(“%d”, &_);
for(int kcase = 1; kcase <= _; kcase++)
{
printf(“Case #%d:\n”, kcase);
int n, Q, st, ed;
scanf(“%d”, &n);
for(int i = 1; i <= n; i++)
{
scanf(“%d”, &arr[i]);
}
sets(n);
scanf(“%d”, &Q);
for(int i = 0; i < Q; i++)
{
scanf(“%d %d”, &st, &ed);
int gg = query(st, ed);
printf(“%d %lld\n”, gg, maps[gg]);
}
}
return 0;
}
/*
1 1 5 1 5
2 2 4 2 3
2 5 5 7 1
3 3 3 4 1
3 4 5 1 7
4 4 4 6 1
4 5 5 7 2
5 5 5 7 3
*/