Problem 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).
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
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
1 8
2 4
2 4
6 1
思路：我们注意观察gcd(al,al+1,...,ar)，当l固定不动的时候，r=l...nr=l...n时，我们可以容易的发现,随着rr的増大，gcd(al,al+1,...,ar)是递减的，同时gcd(al,al+1,...,ar)最多 有log 1000,000,000个不同的值，为什么呢？因为al最多也就有log 1000,000,000个质因数所以我们可以在log级别的时间处理出所有的以L开头的左区间的gcd(al,al+1,...,ar) 那么我们就可以在n log 1000,000,000的时间内预处理出所有的gcd(al,al+1,...,ar)然后我们可以用一个map来记录，gcd值为key的有多少个 然后我们就可以对于每个询问只需要查询对应gcd(al,al+1,...,ar)为多少，然后再在map 里面查找对应答案即可.
代码如下：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <map>
#include <vector>
using namespace std;
int a[]; vector<pair<int,int> > v[];
map<int,long long>ans; int __gcd(int x,int y)
{
int r=x%y;
x=y;
y=r;
if(r==) return x;
return __gcd(x,y);
} int main()
{
int T,Case=;
int n;
cin>>T;
while(T--)
{
ans.clear();
cin>>n;
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=n;i++)
{
int tot=;
for(int j=;j<v[i-].size();j++)
{
int s1=v[i-][j].first;
int s2=v[i-][j].second;
int r=__gcd(a[i],s1);
if(tot==r) continue;
tot=r;
v[i].push_back(make_pair(r,s2));
}
if(tot!=a[i]) v[i].push_back(make_pair(a[i],i));
for(int j=;j<v[i].size();j++)
{
if(j+==v[i].size())
ans[v[i][j].first]+=i+-v[i][j].second;
else
ans[v[i][j].first]+=v[i][j+].second-v[i][j].second;
}
}
cout<<"Case #"<<(++Case)<<":"<<endl;
int Q;
cin>>Q;
while(Q--)
{
int i,l,r;
scanf("%d%d",&l,&r);
for(i=;i<v[r].size();i++)
{
if(v[r][i].second>l) break;
}
printf("%d %I64d\n",v[r][i-].first,ans[v[r][i-].first]);
}
for(int i=;i<;i++)
v[i].clear();
}
return ;
}