链接：http://acm.hdu.edu.cn/showproblem.php?pid=5726
题意：有N（N <= 100,000），之后有Q（Q <= 100,000）个区间查询[l,r]。问ans1 = gcd(al,al+1,...ar) = ?，并且有多少组[l',r'] 的gcd值等于ans1?
思路：
对于求解ans1,由于gcd(a,b,c) = gcd( gcd(a,b),c) 所以可以使用ST表的思想，倍增DP求解区间的gcd值，时间复杂度为O(nlog(n)),之后RMQ查找区间[l,r]的gcd值时，也是和ST表类似；
如果求解个数？
注意到从某个点起的区间的gcd值的变化为非增的；并且每次变化减少的质因子值至少为2，所以个数不超过log(1e9)个；
这时对于从每一个点起使用二分右端点，递推左端点即可在log(n)时间内预处理出[l,n]的所有gcd值，累加到map中，之后O（1）即可；
好题：单调性是一个很好的性质。。
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
#define rep0(i,l,r) for(int i = (l);i < (r);i++)
#define rep1(i,l,r) for(int i = (l);i <= (r);i++)
#define rep_0(i,r,l) for(int i = (r);i > (l);i--)
#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
#define MSi(a) memset(a,0x3f,sizeof(a))
#define inf 0x3f3f3f3f
#define A first
#define B second
#define MK make_pair
#define esp 1e-8
#define zero(x) (((x)>0?(x):-(x))<eps)
#define bitnum(a) __builtin_popcount(a)
#define clear0 (0xFFFFFFFE)
#define mod 1000000007
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
template<typename T>
void read1(T &m)
{
T x = 0,f = 1;char ch = getchar();
while(ch <'0' || ch >'9'){ if(ch == '-') f = -1;ch=getchar(); }
while(ch >= '0' && ch <= '9'){ x = x*10 + ch - '0';ch = getchar(); }
m = x*f;
}
template<typename T>
void read2(T &a,T &b){read1(a);read1(b);}
template<typename T>
void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}
template<typename T>
void out(T a)
{
if(a>9) out(a/10);
putchar(a%10+'0');
}
inline ll gcd(ll a,ll b){ return b == 0? a: gcd(b,a%b); }
const int maxn = 1e5 + 10;
int a[maxn],g[maxn][18];
void ST(int n)
{
rep1(i,1,n) g[i][0] = a[i];
for(int i = 1; i <= 17; i++){
for(int p = 1; p + (1<<i) <= n+1; p++){
g[p][i] = gcd(g[p][i-1],g[p+(1<<i-1)][i-1]);
}
}
}
int RMQ(int l,int r)
{
int len = log(1.*(r-l+1))/log(2);
return gcd(g[l][len],g[r-(1<<len)+1][len]);
}
map<int, ll> mp;
ll solve(int n)
{
mp.clear();
rep1(i,1,n){
for(int j = i;j <= n;j++){
int _gcd = RMQ(i,j), l = j, r = n, tmp = j;
while(l <= r){
int mid = l + r >> 1;
if(RMQ(j,mid) == _gcd) l = mid+1,tmp = mid;
else r = mid - 1;
}
mp[_gcd] += tmp - j + 1;
j = tmp;
}
}
}
int main()
{
//freopen("data.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T, kase = 1;
scanf("%d",&T);
while(T--){
printf("Case #%d:\n", kase++);
int n, m;
read1(n);
rep1(i,1,n) read1(a[i]);
ST(n);
solve(n);
read1(m);
while(m--){
int l, r, aux;
read2(l,r);
aux = RMQ(l,r);
printf("%d %I64d\n",aux,mp[aux]);
}
}
return 0;
}