2818: Gcd

Time Limit: 10 Sec  Memory Limit: 256 MB

Submit: 3241  Solved: 1437

[][][]

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

 

Source

题解：

莫比乌斯函数或欧拉函数。

莫比乌斯函数详见 Popoqqq的课件 (Orz Po姐)

之后就自己推公式吧。。。

莫比乌斯函数：

1 #include
       
         2 using namespace std; 3 #define LL long long 4 #define MAXN 10000010 5 int prime[670010],mu[MAXN],qz[MAXN],tot,N; 6 bitset
        
          vis; 7 int read() 8 { 9     int s=0,fh=1;char ch=getchar();10     while(ch<'0'||ch>'9'){
     if(ch=='-')fh=-1;ch=getchar();}11     while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}12     return s*fh;13 }14 void getmu()15 {16     int i,j;17     mu[1]=1;18     tot=0;19     for(i=2;i<=N;i++)20     {21         if(vis[i]==0)22         {23             prime[++tot]=i;24             mu[i]=-1;25         }26         for(j=1;j<=tot&&prime[j]*i<=N;j++)27         {28             vis[prime[j]*i]=1;29             if(i%prime[j]==0)30             {31                 mu[i*prime[j]]=0;32                 break;33             }34             mu[i*prime[j]]=-mu[i];35         }36     }37 }38 void Qz()39 {40     for(int i=1;i<=N;i++)qz[i]=qz[i-1]+mu[i];41 }42 LL calc(int n)43 {44     int d,pos;45     LL sum=0;46     for(d=1;d<=n;d=pos+1)47     {48         pos=n/(n/d);49         sum+=(LL)(n/d)*(n/d)*(qz[pos]-qz[d-1]);50     }51     return sum;52 }53 int main()54 {55     int i;56     LL ans=0;57     N=read();58     getmu();59     Qz();60     for(i=1;i<=tot&&prime[i]<=N;i++)ans+=calc(N/prime[i]);61     printf("%lld",ans);62     fclose(stdin);63     fclose(stdout);64     return 0;65 }
        
       

 欧拉函数：

1 #include
       
         2 using namespace std; 3 #define MAXN 10000010 4 #define LL long long 5 bitset
        
          vis; 6 int N,prime[670010],phi[MAXN],tot; 7 LL qz[MAXN]; 8 int read() 9 {10     int s=0,fh=1;char ch=getchar();11     while(ch<'0'||ch>'9'){
     if(ch=='-')fh=-1;ch=getchar();}12     while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}13     return s*fh;14 }15 void geteular()16 {17     int i,j;18     phi[1]=1;tot=0;19     for(i=2;i<=N;i++)20     {21         if(vis[i]==0)22         {23             prime[++tot]=i;24             phi[i]=i-1;25         }26         for(j=1;j<=tot&&prime[j]*i<=N;j++)27         {28             vis[prime[j]*i]=1;29             if(i%prime[j]==0)30             {31                 phi[prime[j]*i]=phi[i]*prime[j];32                 break;33             }34             phi[prime[j]*i]=phi[prime[j]]*phi[i];35         }36     }37 }38 void Qz()39 {40     qz[0]=qz[1]=0;41     for(int i=2;i<=N;i++)qz[i]=qz[i-1]+phi[i];42 }43 int main()44 {45     int i,n;46     LL ans=0;47     N=read();48     geteular();49     Qz();50     for(i=1;i<=tot;i++)51     {52         n=N/prime[i];53         ans+=(qz[n]*2+1);54     }55     printf("%lld",ans);56     fclose(stdin);57     fclose(stdout);58     return 0;59 }