2818: Gcd
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 3241 Solved: 1437
[Submit][Status][Discuss]
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姐)
之后就自己推公式吧。。。
莫比乌斯函数：
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define MAXN 10000010
int prime[],mu[MAXN],qz[MAXN],tot,N;
bitset<MAXN> vis;
int read()
{
int s=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
return s*fh;
}
void getmu()
{
int i,j;
mu[]=;
tot=;
for(i=;i<=N;i++)
{
if(vis[i]==)
{
prime[++tot]=i;
mu[i]=-;
}
for(j=;j<=tot&&prime[j]*i<=N;j++)
{
vis[prime[j]*i]=;
if(i%prime[j]==)
{
mu[i*prime[j]]=;
break;
}
mu[i*prime[j]]=-mu[i];
}
}
}
void Qz()
{
for(int i=;i<=N;i++)qz[i]=qz[i-]+mu[i];
}
LL calc(int n)
{
int d,pos;
LL sum=;
for(d=;d<=n;d=pos+)
{
pos=n/(n/d);
sum+=(LL)(n/d)*(n/d)*(qz[pos]-qz[d-]);
}
return sum;
}
int main()
{
int i;
LL ans=;
N=read();
getmu();
Qz();
for(i=;i<=tot&&prime[i]<=N;i++)ans+=calc(N/prime[i]);
printf("%lld",ans);
fclose(stdin);
fclose(stdout);
return ;
}
欧拉函数：
#include<bits/stdc++.h>
using namespace std;
#define MAXN 10000010
#define LL long long
bitset<MAXN> vis;
int N,prime[],phi[MAXN],tot;
LL qz[MAXN];
int read()
{
int s=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
return s*fh;
}
void geteular()
{
int i,j;
phi[]=;tot=;
for(i=;i<=N;i++)
{
if(vis[i]==)
{
prime[++tot]=i;
phi[i]=i-;
}
for(j=;j<=tot&&prime[j]*i<=N;j++)
{
vis[prime[j]*i]=;
if(i%prime[j]==)
{
phi[prime[j]*i]=phi[i]*prime[j];
break;
}
phi[prime[j]*i]=phi[prime[j]]*phi[i];
}
}
}
void Qz()
{
qz[]=qz[]=;
for(int i=;i<=N;i++)qz[i]=qz[i-]+phi[i];
}
int main()
{
int i,n;
LL ans=;
N=read();
geteular();
Qz();
for(i=;i<=tot;i++)
{
n=N/prime[i];
ans+=(qz[n]*+);
}
printf("%lld",ans);
fclose(stdin);
fclose(stdout);
return ;
}