GCD

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 4549 Accepted Submission(s): 1630

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).

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 

Author

HIT

Source

思路：定义f[i][j]为：ai开始，连续2^j个数的最大公约数，令k=log2(r-l+1)，

则look(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），二分j， i-j都是同一个gcd值，然后直接加到map中。

#include
    
     #include
     
      #include
      using namespace std;int f[100010][18];int a[100010];int n,m;int gcd(int a,int b){ return b?gcd(b,a%b):a;}void rmq(){	for(int j=1;j<=n;j++) f[j][0]=a[j];	for(int i=1;i<18;i++)	{		for(int j=1;j<=n;j++)		  {		  	if(j+(1<
       
        <=n) f[j][i]=gcd(f[j][i-1],f[j+(1<
        
         mp;void ta(){	mp.clear();	for(int i=1;i<=n;i++)	  {	  	int g=f[i][0],j=i;	  	while(j<=n)	  	  {	  	  	int l=j,r=n;	  	  	while(l
         
          >1; if(look(i,mid)==g) l=mid; else r=mid-1; } mp[g]+=l-j+1; j=l+1; g=look(i,j); } }}int main(){ int t,l,r; int cas=1; scanf("%d",&t); while(t--) { printf("Case #%d:\n",cas++); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); rmq(); ta(); scanf("%d",&m); for(int i=0;i