多校 GCD

101 阅读 0 评论 67 点赞

我是靠谱客的博主痴情抽屉，最近开发中收集的这篇文章主要介绍多校 GCD，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

Sample Output

我们注意观察

gcd(a_{l},a_{l+1},...,a_{r})

，当l固定不动的时候，

r = l . . . n

时，我们可以容易的发现,随着

r

的増大，

gcd(a_{l},a_{l+1},...,a_{r})

是递减的，同时

gcd(a_{l},a_{l+1},...,a_{r})

最多有

l o g 1000, 000, 000

个不同的值，为什么呢？因为

a_{l}

最多也就有

l o g 1000, 000, 000

个质因数

所以我们可以在log级别的时间处理出所有的以L开头的左区间的 $gcd(a_{l},a_{l+1},...,a_{r})$ 那么我们就可以在 $n l o g 1000, 000, 000$ 的时间内预处理出所有的 $gcd(a_{l},a_{l+1},...,a_{r})$ 然后我们可以用一个map来记录，gcd值为key的有多少个然后我们就可以对于每个询问只需要查询对应 $gcd(a_{l},a_{l+1},...,a_{r})$ 为多少，然后再在map 里面查找对应答案即可.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <algorithm>
#include <cmath>
#include <ctime>
#define LL long long

using namespace std;
int a[110000];
//pair.first为求的GCD
//pair.second为区间的R
//vec对应的下标为区间的L
vector<pair<int,int> >vec[110000];
map<int,LL>M;
int main()
{
    int T,t=0;
    int l,r;
    int n,m;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i = 1; i <= n; ++i){
            scanf("%d",&a[i]);
            vec[i].clear();
        }

        M.clear();
        for(int i = n; i >= 1; i--){
            int g = 0;
            /*
            L+1....R3...R2....R1....R0
            L+1....R3区间的GCD相同
            L+1....R3+1和L...R3+2和...和L+1....R2的GCD相同
            L+1....R2+1和L...R2+2和...和L+1....R1的GCD相同
            L+1....R1+1和L...R1+2和...和L+1....R0的GCD相同
            假设L+k<R3
            __gcd(a[l],[L+1,L+k])和__gcd(a[l],[L+1,R3])相同
            所以只需计算__gcd(a[l],[L+1,R3])的gcd就求出了[L,R3]的GCD了,他们相同。
            以此类推...
            */
            for(int j = 0; j < vec[i+1].size(); ++j){
                int x = vec[i+1][j].first;
                int y = vec[i+1][j].second;
                int d = __gcd(x,a[i]);
                if(g==d)continue;
                g = d;
                vec[i].push_back(make_pair(g,y));
            }
            //[i,i]区间也是一个GCD
            if(g!=a[i])vec[i].push_back(make_pair(a[i],i));
            //用map记录gcd值出现了几次
            for(int j = 0; j < vec[i].size(); ++j){
                //区间[i,vec[i][j].second] 的 gcd 为 vec[i][j].first
                if(j+1 != vec[i].size())
                    M[vec[i][j].first] += (LL)(vec[i][j].second-vec[i][j+1].second);
                else{
                    M[vec[i][j].first] += (LL)(vec[i][j].second-i+1);
                }
            }
        }
        scanf("%d",&m);
        printf("Case #%d:n",++t);
        while(m--){
            scanf("%d%d",&l,&r);
            int x = vec[l].size()-1;
            for(int i = 0; i < vec[l].size(); ++i){
                if(vec[l][i].second < r){
                    x = i-1;
                    break;
                }
            }
            printf("%d %lldn",vec[l][x].first,M[vec[l][x].first]);
        }
    }
    return 0;
}