本文共 1032 字，大约阅读时间需要 3 分钟。

Description

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

Input

一个整数N

Output

如题

Sample Input

4

Sample Output

4

HINT

对于样例(2,2),(2,4),(3,3),(4,2)

1<=N<=10^7

题解

重学莫反

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;typedef long long LL;int mu[11000000],prime[11000000],pr,n;bool v[11000000];void getmu(){    memset(v,true,sizeof(v));    mu[1]=1;pr=0;    for(int i=2;i<=10000000;i++)    {        if(v[i]==true)        {            prime[++pr]=i;            mu[i]=-1;        }        for(int j=1;i*prime[j]<=10000000 && j<=pr;j++)        {            v[i*prime[j]]=false;            if(i%prime[j]==0)            {                mu[i*prime[j]]=0;                break;            }            else mu[i*prime[j]]=-mu[i];        }    }}int main(){    scanf("%d",&n);    getmu();LL ans=0;    for(int i=1;prime[i]<=n;i++)    {        for(LL j=1;j<=(LL)n/prime[i];j++)            ans+=(LL)mu[j]*((n/prime[i])/j)*((n/prime[i])/j);    }    printf("%lld\n",ans);    return 0;}