Description
Give you a sequence of N(N≤100,000) integers : a1,...,an(0<ai≤1000,000,000). There are Q(Q≤100,000) queries. For each query l,r you have to calculate gcd(al,,al+1,...,ar) and count the number of pairs(l′,r′)(1≤l<r≤N)such that gcd(al′,al′+1,...,ar′) equal gcd(al,al+1,...,ar).
Input
The first line of input contains a number T, which stands for the number of test cases you need to solve.
The first line of each case contains a number N, denoting the number of integers.
The second line contains N integers, a1,...,an(0<ai≤1000,000,000).
The third line contains a number Q, denoting the number of queries.
For the next Q lines, i-th line contains two number , stand for the li,ri, stand for the i-th queries.
Output
For each case, you need to output “Case #:t” at the beginning.(with quotes, t means the number of the test case, begin from 1).
For each query, you need to output the two numbers in a line. The first number stands for gcd(al,al+1,...,ar) and the second number stands for the number of pairs(l′,r′) such that gcd(al′,al′+1,...,ar′) equal gcd(al,al+1,...,ar).
Sample Input
1
5
1 2 4 6 7
4
1 5
2 4
3 4
4 4
Sample Output
Case #1:
1 8
2 4
2 4
6 1
//2016.8.9
#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
#include<cmath> using namespace std; typedef long long ll;
const int N = ;
int dp[N][];//d[i][j]表示从第i个数字开始向后2^j个数字这段区间内的gcd,具有递减性
map<int, ll> mp; void init_rmq(int n)//初始化dp,求出每段区间的gcd
{
for(int j = ; j < (int)log2(n)+; j++)
for(int i = ; i <= n; i++)
{
if(i+(<<j)- <= n)
dp[i][j] = __gcd(dp[i][j-], dp[i+(<<(j-))][j-]);
}
} int rmq(int l, int r)//查询
{
int k = (int)log2(r-l+);
return __gcd(dp[l][k], dp[r-(<<k)+][k]);
} int main()
{
int n, q, l, r, T, kase = ;
cin>>T;
while(T--)
{
printf("Case #%d:\n", ++kase);
cin>>n;
mp.clear();
for(int i = ; i <= n; i++)
scanf("%d", &dp[i][]);
init_rmq(n); //利用二分求具有相同gcd区间的数目
//-----------------------------------------------------------------------------------
for(int i = ; i <= n; i++)
{
int a = i, b = n, mid, tmp, vs;
while()
{
tmp = a;
vs = rmq(i, a);
while(a <= b)
{
mid = (a+b)>>;
if(rmq(i, mid)<vs) b = mid-;
else a = mid+;
}
mp[vs]+=1ll*(b-tmp+);
b = n;
if(a>b)break;
}
}
//------------------------------------------------------------------------------------ cin>>q;
while(q--)
{
scanf("%d%d", &l, &r);
int ans = rmq(l, r);
cout<<ans<<" "<<mp[ans]<<endl;
}
} return ;
}