| Time Limit: 5000MS | Memory Limit: 65536KB | 64bit IO Format: %I64d & %I64u |
Description
Give you a sequence of N(N \leq 100, 000) integers : a_{1},...,a_{n}(0 < a_{i} \leq 1000, 000, 000). There are Q (Q \leq 100, 000) queries. For each query l, r you have to calculate gcd(a_{l},,a_{l+1},...,a_{r}) and count the number of pairs(l’, r’) (1 \leq l < r \leq N)such thatgcd(a_{l’},a_{l’+1},...,a_{r’}) equal gcd(a_{l},a_{l+1},...,a_{r}).
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, a_{1},...,a_{n}(0 < a_{i} \leq 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 l_{i}, r_{i}, stand for the i-th queries.
The first line of each case contains a number N, denoting the number of integers.
The second line contains N integers, a_{1},...,a_{n}(0 < a_{i} \leq 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 l_{i}, r_{i}, 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(a_{l},a_{l+1},...,a_{r}) and the second number stands for the number of pairs(l’, r’) such that gcd(a_{l’},a_{l’+1},...,a_{r’}) equal gcd(a_{l},a_{l+1},...,a_{r}).
For each query, you need to output the two numbers in a line. The first number stands for gcd(a_{l},a_{l+1},...,a_{r}) and the second number stands for the number of pairs(l’, r’) such that gcd(a_{l’},a_{l’+1},...,a_{r’}) equal gcd(a_{l},a_{l+1},...,a_{r}).
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
Source
2016 Multi-University Training Contest 1
题意：给一个数组a，大小为n，接下来有m个询问，每次询问给出l、r，定义f[l,r]=gcd（al，al+1，...，ar），问f[l,r]的值 和 有多少对（l'，r'）使得f[l',r']=f[l,r]。1<=l<=r<=n，题目中给的数据过大，不可直接使用dp方程。
思路：
第一步，RMQ预处理一下，定义f[i][j]为：ai开始，连续2^j个数的最大公约数，所以f[1][0]=a[1],f[1][1]=gcd(a1,a2),f[1][2]=gcd(a1,a2,a3,a4)。递推即可。
递推公式如下：
1. f[i][0]=a[i];
2. f[i][j]=gcd(f[i][j-1],f[i+(1<<(j-1))][j-1])
接着查询时就只需O(1)时间，如下：
令k=log2(r-l+1)，RMQ(l,r)=gcd(f[l][k],f[r-(1<<k)+1][k]);
注：f[l][k] 和 f[r-(1<<k)+1][k]可能会有重叠，但不影响最终的gcd值。
第二步二分法：我们可以枚举左端点 i 从1-n，对每个i，二分右端点，计算每种gcd值的数量，因为如果左端点固定，gcd值随着右端点的往右，呈现单调不增，这点很重要，比赛时没有想到，而且gcd值每次变化，至少除以2，所以gcd的数量为nlog2(n)种，可以开map<int,long long>存每种gcd值的数量，注意n大小为10万，所以有可能爆int。
#include<stdio.h>
#include<math.h>
#include<map>
using namespace std;
int f[][];
int a[];
int n,m;
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
void rmq()
{
for(int i=; i<=n; i++) f[i][]=a[i];
for(int j=; (<<j)<=n; j++)
{
for(int i=; i+(<<j)-<=n; i++)
{
f[i][j]=gcd(f[i][j-],f[i+(<<(j-))][j-]);
}
}
}
int RMQ(int l,int r)
{
int k=;
while((<<(k+))<=r-l+) k++;
return gcd(f[l][k],f[r-(<<k)+][k]);
}
map<int,long long> mp;
void setTable()
{
mp.clear();
for(int i=; i<=n; i++)
{
int g=f[i][],j=i;
while(j<=n)
{
int l=j,r=n;
while(l<r)
{
int mid=(l+r+)>>;
if(RMQ(i,mid)==g) l=mid;
else r=mid-;
}
mp[g]+=l-j+;
j=l+;
g=RMQ(i,j);
}
}
}
int main()
{
int t,l,r;
int cas=;
scanf("%d",&t);
while(t--)
{
printf("Case #%d:\n",cas++);
scanf("%d",&n);
for(int i=; i<=n; i++)
{
scanf("%d",&a[i]);
}
rmq();
setTable();
scanf("%d",&m);
for(int i=; i<m; i++)
{
scanf("%d%d",&l,&r);
int g=RMQ(l,r);
printf("%d %I64d\n",g,mp[g]);
}
}
return ;
}