Gcd反应堆 (pgcd)

题目描述

不知什么时候起，TA突然对gcd产生了浓厚的兴趣，于是他为此编写了个程序，输入分别不大于m,n (1<m,n<=10^7)的两个数，就能得出gcd(m,n)！TA兴奋之余，给这个程序起了个酷(zhuang)雅(bi)的名字：gcd反应堆。

现在TA要做一项伟大的科学实验，需要大量素数，他打算生成素数这种任务就交给他的反应堆实现。现在TA问你，多少对在他反应堆承载范围内的整数对i,j (1<i<=m,1<=j<=n)，生成的数是他所需要的原料呢？

输入

本题包含多组数据，第一行包含一个整数t，表示数据组数。

接下来T行，每行两个整数m,n，意义为题目所述。

输出

输出T行，每行一个整数，为满足(1<i<=m,1<=j<=n)且gcd(i,j)为素数的整数对(i,j)的个数。

【数据规模】

对于30%的数据，m,n<=10^3

对于70%的数据，m,n<=10^5

对于100%的数据额，m,n<=10^7,T<=10

---

solution

题目求

先枚举质数p

除掉p

套用反演的式子

先枚举gcd

后面可以O(1)算，前面O（n）预处理mu

效率O（nlogn）

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

int T,n,m,mu[10000007],pri[10000007],tot;

bool flag[10000007];

int main()

{

    int Max=10000000;mu[1]=1;

    for(int i=2;i<=Max;i++){

        if(!flag[i]){mu[i]=-1;pri[++tot]=i;}

        for(int j=1;j<=tot&&i<=Max/pri[j];j++){

            flag[i*pri[j]]=1;mu[i*pri[j]]=-mu[i];

            if(i%pri[j]==0){mu[i*pri[j]]=0;break;}

        }

    }

    cin>>T;

    while(T--){

        scanf("%d%d",&n,&m);

        if(n<m)swap(n,m);

        long long ans=0;

        for(int i=1;i<=tot&&pri[i]<=m;i++){

            int p=pri[i];

            for(int d=1;p<=m/d;d++){

                ans=ans+(1LL)*mu[d]*(n/(p*d))*(m/(p*d));

            }

        }

        cout<<ans<<endl;

    }

    return 0;

}