GCD

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 1497    Accepted Submission(s): 483

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

1

思路：RMQ+二分

一开始我用的线段树去维护各个区间的gcd但是超时，并且我没有优化。

暴力统计的各个区间的gcd；

后来发现gcd的性质，也就是求数的gcd，这些数的个数越多那么gcd越小，所以从左到右，以某个端点开始的gcd的大小随着区间增大而减小，那么二分统计以某个点为端点的gcd

最多每个端点二分30次。

然后还是超时。

然后改用RMQ基于稀疏表的，查询O（n）；

复杂度（n*log(n)）;

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include