洛谷P2568 GCD（欧拉定理 | | 莫比乌斯反演）

题目描述

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

输入输出样例

输入样例#1： 4 输出样例#1： 4

题解

此题有两种解法。 1.欧拉函数 很明显，可以枚举素数p，计算n/p的phi，然后统计出来乘以2，最后再特判x==y且x,y为素数的情况。

#include<bits/stdc++.h> #define ll long long using namespace std; int n,cnt; ll phi[10000001]; int vis[10000001]; int prime[10000001]; ll sum=0; void init(){ for(register int i=2;i<=n;i++){ if(!vis[i]){ prime[++cnt]=i; phi[i]=i-1; } for(register int j=1;j<=cnt&&i*prime[j]<=n;j++){ int k=i*prime[j]; vis[k]=1; if(i%prime[j]==0){ phi[k]=phi[i]*prime[j]; break; } else{ phi[k]=phi[i]*(prime[j]-1); } } phi[i]=phi[i-1]+(phi[i]<<1); } } int main(){ scanf("%d",&n); init(); for(register int i=1;i<=cnt;i++){ sum+=phi[n/prime[i]]+1; } printf("%lld",sum); return 0; }

2.莫比乌斯反演 当1<=x<=n,1<=y<=m时，欧拉函数的求法就不管用了，这时我们可以用莫比乌斯反演来简化计算。 我们设

f(n)=∑d|n[gcd(x,y)==d] 设 F(n)=∑d|nf(d) 根据莫比乌斯反演定理可得 f(n)=∑d|nμ(n/d)∗F(d) 而 F(d) 的值可以通过它的定义发现 F(d)=(n/d)∗(n/d) 即 f(n)=∑d|nμ(n/d)∗((n/d)∗(n/d)) 枚举质数，暴力累计答案即可。 （此方法在洛谷70，TLE*3，在bzojAC） 此题升级版： 洛谷P3455

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<cmath> #include<vector> #include<queue> #define ll long long using namespace std; int mu[10000001]; int cnt; bool vis[10000001]; int prime[5000001]; void init(int n){ mu[1]=1; for(int i=2;i<=n;i++){ if(!vis[i]){ prime[++cnt]=i; mu[i]=-1; } for(int j=1;j<=cnt&&i*prime[j]<=n;j++){ int k=i*prime[j]; vis[k]=1; if(i%prime[j]){ mu[k]=-mu[i]; } else{ mu[k]=0; break; } } } } int main(){ ll n; scanf("%lld",&n); init(n); ll ans=0; for(ll i=1;i<=cnt;i++){ ll lim=n/prime[i]; for(ll j=1;j<=lim;j++){ ans+=mu[j]*((lim)/j)*((lim)/j); } } printf("%lld",ans); return 0; }

考虑优化。 我不会推公式，就借dalao的公式一用吧（滑稽） 然后就可以分块搞了。。。 （其实跑的还挺快的，时间和欧拉几乎相同）

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<cmath> #include<vector> #include<queue> #define ll long long using namespace std; int mu[10000001]; int cnt; bool vis[10000001]; int prime[5000001]; void init(int n){ mu[1]=1; for(int i=2;i<=n;++i){ if(!vis[i]){ prime[++cnt]=i; mu[i]=-1; } for(int j=1;j<=cnt&&i*prime[j]<=n;++j){ int k=i*prime[j]; vis[k]=1; if(i%prime[j]){ mu[k]=-mu[i]; } else{ mu[k]=0; break; } } mu[i]+=mu[i-1]; } } int main(){ ll n; scanf("%lld",&n); init(n); ll ans=0; for(ll k=1;k<=cnt;++k){ ll m=n/prime[k]; ll j; for(ll i=1;i<=m;i=j+1){ ll mul=m/i; j=min(m,m/mul); ans+=mul*mul*(mu[j]-mu[i-1]); } } printf("%lld",ans); return 0; }