bzoj 2818（莫比乌斯）

Description

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

 

Input

一个整数N

Output

如题

Sample Input

4  

Sample Output

4

HINT

 

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

 

1<=N<=10^7

思路：GCD(a,b)=d   (d是素数)，设f(d) = GCD(a,b) = d的种类数 ，F(n) 为GCD(a,b) = d 的倍数的种类数，GCD(a,b)%d==0; F(x) = (N/x)*(N/x);f(x) = sigma( mu[d/x]*F(d), d|n )，由于d = 1 所以f(1) = sigma( mu[d]*F(p*d) ) = sigma( mu[d]*(N/pd)*(N/pd) ); （其中p为枚举的素数，利用素数优化就能过了）

代码：

#include<bits/stdc++.h> using namespace std; typedef long long LL; const LL N=1e7+10; bool vis[N]; LL prime[N],mu[N]; LL cnt; void Init() {     memset(vis,0,sizeof(vis));     mu[1] = 1;     cnt = 0;     for(LL i=2; i<N; i++)     {         if(!vis[i])         {             prime[cnt++] = i;             mu[i] = -1;         }         for(LL j=0; j<cnt&&i*prime[j]<N; j++)         {             vis[i*prime[j]] = 1;             if(i%prime[j]) mu[i*prime[j]] = -mu[i];             else             {                 mu[i*prime[j]] = 0;                 break;             }         }     } } int main() {     LL n;     Init();     while(scanf("%lld",&n)!=EOF)     {         LL ans=0;         for(LL i=0;prime[i]<=n;i++)         {             for(LL j=1;j<=n/prime[i];j++)             {                 ans+=(LL)(mu[j]*(n/prime[i]/j)*(n/prime[i]/j));             }         }         printf("%lld\n",ans);     }     return 0; }