BZOJ2820: YY的GCD

【传送门：BZOJ2820】

简要题意：

　　给出n,m，求出满足x<=n,y<=m的数对中gcd(x,y)为质数的数对数

题解：

　　莫比乌斯反演

　　设F(t)为gcd(x,y)%t==0的数对数，f(t)为gcd(x,y)==t的数对数，F(t)=(n/i)*(m/i)

　　然后可以得到$F(n)=sum_{n|d}f(d)$，根据公式得到$f(x)=sum_{x|d}mu(frac{d}{x})frac{n}{d}*frac{m}{d}$

　　再令上一个式子中的x=p,d=p*i，设v(p)表示p是否为质数，就可以得到$$ans=sum_{v(p)}^n sum_i^n frac{n}{p*i}*frac{m}{p*i}mu(i)$$ $x = p$

　　再设T=p*i，然后交换和式，就得到$$ans=sum_{T}^{n} frac{n}{T}*frac{m}{T}sum_{p|T且v(p)}mu(frac{T}{p})$$

　　显然$sum_{p|T且v(p)}mu(frac{T}{p})$这个东西可以用前缀和预处理一下

　　然后整除分块就好了

参考代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
int miu[11000000],prime[1100000],v[11000000];
LL sum[11000000];
void pre(int n)
{
    memset(v,0,sizeof(v));
    memset(miu,0,sizeof(miu));miu[1]=1;
    int m=0;
    for(int i=2;i<=n;i++)
    {
        if(v[i]==0)
        {
            v[i]=i;
            prime[++m]=i;
            miu[i]=-1;
        }
        for(int j=1;j<=m;j++)
        {
            if(prime[j]>v[i]||prime[j]>n/i) break;
            v[i*prime[j]]=prime[j];
            if(i%prime[j]==0) miu[i*prime[j]]=0;
            else miu[i*prime[j]]=-miu[i];
        }
    }
    sum[0]=0;
    for(int i=1;i<=m;i++) for(int j=1;prime[i]*j<=n;j++) sum[prime[i]*j]+=miu[j];
    for(int i=1;i<=n;i++) sum[i]+=sum[i-1];
}
int main()
{
    pre(10000000);
    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 i=1,j;i<=n;i=j+1)
        {
            j=min(n/(n/i),m/(m/i));
            ans+=(LL)(n/i)*(m/i)*(sum[j]-sum[i-1]);
        }
        printf("%lld
",ans);
    }
    return 0;
}