P2257 YY的GCD（莫比乌斯反演）

题目链接

题意：

给定 $N,M$，求 $1\le x\le N，1\le y\le M$ 且 $\gcd (x,y)$为质数的 $(x,y)$ 有多少对。
$T$组样例，$T=10^4,N,M\le 10^7$

推导：

根据题意写出式子，

${\sum }_{i=1}^N{\sum }_{j=1}^M[gcd(i,j)为质数]$

提出$gcd$， 变成

${\sum }_{g=1}^{min(N,M)}{\sum }_{i=1}^N{\sum }_{j=1}^M[gcd(i,j)=g][g为质数]$

不妨让$N<M$

就变成${\sum }_{g=1}^N[g为质数]{\sum }_{i=1}^N{\sum }_{j=1}^M[gcd(i,j)=g]$了，写起来舒服点。

令$f(g)={\sum }_{i=1}^N{\sum }_{j=1}^M[gcd(i,j)=g]$

令$F(g)={\sum }_{g|d}f(d)={\sum }_{i=1}^N{\sum }_{j=1}^M[g|gcd(i,j)]=\lfloor \frac{N}{g}\rfloor \lfloor \frac{M}{g}\rfloor$

根据莫比乌斯反演公式有$f(g)={\sum }_{g|d}\mu (\frac{d}{g})F(d)$

代回原式子得，

${\sum }_{g=1}^N[g为质数]f(g)={\sum }_{g=1}^N[g为质数]{\sum }_{g|d}\mu (\frac{d}{g})\lfloor \frac{N}{d}\rfloor \lfloor \frac{M}{d}\rfloor$

                                      $={\sum }_{d=1}^N\lfloor \frac{N}{d}\rfloor \lfloor \frac{M}{d}\rfloor {\sum }_{g|d}\mu (\frac{d}{g})[g为质数]$

                                      $={\sum }_{d=1}^N\lfloor \frac{N}{d}\rfloor \lfloor \frac{M}{d}\rfloor S(d)$

其中我们令$S(d)={\sum }_{g|d}\mu (\frac{d}{g})[g为质数]$，我们只要预处理出$S(d)$， 再处理出$S(d)$的前缀和，就可以用数论分块求答案了。

那么预处理$S(d)$，我们可以对于每个数分解质因子计算贡献，也可以对于每个质数，把贡献加到它的所有倍数中，两种做法都可以$o(nlogn)$。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
typedef pair<int,int> P;
const int MAXN=10000000;

int prime[MAXN+10],notPrime[MAXN+10],mu[MAXN+10],tot;
void initMu(int n)
{
    
    notPrime[1]=mu[1]=1;
    for(int i=2;i<=n;i++)
    {
    
        if(!notPrime[i])prime[tot++]=i,mu[i]=-1;
        for(int j=0;j<tot&&i*prime[j]<=n;j++)
        {
    
            notPrime[i*prime[j]]=1;
            if(i%prime[j])mu[i*prime[j]]=-mu[i];
            else {
    mu[i*prime[j]]=0;break;}
        }
    }
}

int f[MAXN+10];
int main()
{
    
    initMu(MAXN);
    for(int i=1;i<=MAXN;i++)if(!notPrime[i])
    {
    
        for(int j=i;j<=MAXN;j+=i)
        {
    
            f[j]+=mu[j/i];
        }
    }
    for(int i=1;i<=MAXN;i++)f[i]+=f[i-1];
    int T;
    scanf("%d",&T);
    while(T--)
    {
    
        int n,m;
        scanf("%d%d",&n,&m);
        if(n>m)swap(n,m);
        ll ans=0;
        for(int l=1,r;l<=n;l=r+1)
        {
    
            r=min(n/(n/l),m/(m/l));
            ans=ans+1ll*(n/l)*(m/l)*(f[r]-f[l-1]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}