[BZOJ2818/Luogu2568] gcd (莫比乌斯反演)

发布于 2018-01-19  174 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2818/Luogu2568] gcd (莫比乌斯反演)

Description

给定整数N,求1<=x,y<=N且Gcd(x,y)为素数的
数对(x,y)有多少对.

Tag

莫比乌斯反演

题目大意

求\(\sum_{i=1}^{n} \sum_{j=1}^{m} [gcd(i,j)\ is\ a\ prime]\)

解决思路

设\( f(d)=\begin{cases} 1 \quad d\ is\ a\ prime \\ 0 \quad\ d\ is\ not\ a\ prime\end{cases}\)
提取$$gcd(i,j)==d$$,得到
\[Ans=\sum_{d=1}^{n} f(d)*\sum_{i=1}^{n} \sum_{j=1}^{m} [gcd(i,j)==1]\]
根据以前(这里)推出的式子,由莫比乌斯反演得
\[Ans=\sum_{d=1}^{n} f(d)*\sum_{i=1}^{n/d} \mu(i) \lfloor \frac{n}{id} \rfloor^2\]
那么记一下质数个数的前缀和以及\(\mu()\)的前缀和前后两层数论分块即可

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxNum=10000010;
const int inf=2147483647;

int Mu[maxNum],Musum[maxNum];
int Prisum[maxNum];
int pricnt=0,Prime[maxNum/1000];
bool notprime[maxNum];

void Init();//线性筛求mu
ll Calc(int n);//内层分块

int main()
{
    Init();
    int n;scanf("%d",&n);
    ll ans=0;
    for (ll i=1,last;i<=n;i=last+1)
    {
        last=n/(n/i);//外层分块
        ans=ans+(Prisum[last]-Prisum[i-1])*Calc(n/i);
    }
    printf("%lld\n",ans);
    return 0;
}

void Init()
{
    notprime[1]=1;Mu[1]=1;
    for (int i=2;i<maxNum;i++)
    {
        if (notprime[i]==0) Prime[++pricnt]=i,Mu[i]=-1,Prisum[i]=1;
        for (int j=1;(j<=pricnt)&&((ll)i*(ll)Prime[j]<maxNum);j++)
        {
            notprime[i*Prime[j]]=1;
            if (i%Prime[j]==0) break;
            Mu[i*Prime[j]]=-Mu[i];
        }
    }
    for (int i=1;i<maxNum;i++) Musum[i]=Musum[i-1]+Mu[i],Prisum[i]+=Prisum[i-1];
    return;
}

ll Calc(int n)
{
    ll ret=0;
    for (ll i=1,last;i<=n;i=last+1)
    {
        last=n/(n/i);
        ret=ret+(Musum[last]-Musum[i-1])*(ll)((n/i))*(ll)((n/i));
    }
    //cout<<n<<" "<<ret<<endl;
    return ret;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2818/Luogu2568] gcd (莫比乌斯反演)


HNCJ OIer