题目链接

大意

给定多组\(N\)，\(M\)，求\(1\le x\le N,1\le y\le M\)并且\(Gcd(x, y)\)为质数的\((x, y)\)有多少对。

思路

我们设\(f(i)\)表示\(Gcd(x,y)=i\)的\((x,y)\)的个数，\(F(i)\)表示\(Gcd(x,y)\%i=0\)的\((x,y)\)的个数。
那么有\[F(i)=\lfloor\frac{N}{i}\rfloor\lfloor\frac{M}{i}\rfloor=\sum_{i\mid d}f(d)\]，
用莫比乌斯反演得到：\[f(i)=\sum_{i\mid d}\mu(\frac{d}{i})\cdot F(d)\]

那么我们要求的\(Ans\)就为：\[Ans=\sum_{p\in prime}f[p]=\sum_{p\in prime}\sum_{p\mid d}\mu(\frac{d}{p})\cdot F(d)\]
即\[Ans=\sum_{p\in prime}\sum_{p\mid d}\mu(\frac{d}{p})\cdot \lfloor\frac{N}{d}\rfloor\lfloor\frac{M}{d}\rfloor\]
上述化简式对于单组数据已经够了，然而，对于多组数据依然有较大的缺陷，考虑优化。

对上述式子变形：\[Ans=\sum_{d=1}^{min(N,M)}\lfloor\frac{N}{d}\rfloor\lfloor\frac{M}{d}\rfloor\cdot(\sum_{p\in prime\&p\mid d}\mu(\frac{d}{p}))\]
对于后面的式子，我们可以预先处理好对于每个\(d\)的总和，然后发现前面为一个数论分块，所以可以\(O(T\sqrt{N})\)算。

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const long long ONE=1;
const int MAXV=10000000;
const int MAXN=10000005;
int T,A,B,Miu[MAXN];
long long Sum[MAXN];
int Pcnt,Prime[MAXN],visp[MAXN];
long long Ans;
void Prepare(){
    visp[0]=visp[1]=1;Miu[1]=1;
    for(int i=2;i<=MAXV;i++){
        if(!visp[i]){Prime[++Pcnt]=i;Miu[i]=-1;}
        for(int j=1;j<=Pcnt&&i*Prime[j]<=MAXV;j++){
            visp[i*Prime[j]]=1;
            if(i%Prime[j]==0){
                Miu[i*Prime[j]]=0;
                break;
            }
            else Miu[i*Prime[j]]=-Miu[i];
        }
    }
    for(int i=1;i<=Pcnt;i++)
        for(int j=1;j*Prime[i]<=MAXV;j++)
            Sum[j*Prime[i]]+=Miu[j];
    for(int i=1;i<=MAXV;i++)
        Sum[i]=Sum[i-1]+Sum[i];
}
int main(){
    Prepare();
    scanf("%d",&T);
    while(T--){Ans=0;
        scanf("%d%d",&A,&B);
        int lowin=min(A,B);
        for(int L=1,R;L<=lowin;L=R+1){
            R=min(A/(A/L),B/(B/L));
            Ans+=(Sum[R]-Sum[L-1])*(A/L)*(B/L);
        }
        printf("%lld\n",Ans);
    }
}

【BZOJ2820】YY的GCD(莫比乌斯反演 数论分块)

原文：https://www.cnblogs.com/ftotl/p/11869127.html