欧拉函数φ

sadlin / 2024-09-24 / 原文

欧拉函数定理

欧拉函数，即 $\varphi(n)$，表示的是小于等于 $n$ 和 $n$ 互质的数的个数，详细定义看wiki。

欧拉函数其实就是容斥原理的应用，举个例子：

如 $n=6$，$1,2,3,4,5,6$ 是整个序列，我们将 $6$ 的质因子 $2$，$3$ 取出，减去小于等于 $6$ 的 $2$ 的倍数和 $3$ 的倍数，但是 $2$ 和 $3$ 的公倍数 $6$ 被减了两次所以还要再加一次：$6-\frac{6}{2}-\frac{6}{3}+\frac{6}{6}=2$

将这个公式转化一下就可以得到通用公式（$p$ 为 $n$ 的质因数）:

\[\varphi(n)=n\times (1- \frac{n}{p_1})\times (1- \frac{n}{p_2}) \times ……\times (1- \frac{n}{p_k}) \]

acwing原题链接

看什么代码，自己写

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,m;
int main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
    	cin>>n;
	    m=n;
	    for(int i=2;i*i<=n;i++){
	    	if(n%i==0){
	    		m*=(1-1.0/i);
				while(n%i==0){
					n/=i;
				}
			}
		}
		if(n>1){
			m*=(1-1.0/n);
		}
		cout<<m<<"\n";
	}

    return 0;
}

用线性筛求欧拉函数：

求 $1-n$ 所有数的欧拉函数的总和。

注意点是 $1-n$ 所有的数与欧拉函数质因子的性质就和欧拉筛相符（应该不是巧合），所以在求质数的时候向后更新欧拉函数值。

这个就不用再分别讨论列举了吧。

acwing原题链接

给你看看代码吧

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e7;
int n;
int is[N];
int p[N];
ll phi[N];
int cnt;

ll solve(){
	phi[1]=1;
	for(int i=2;i<=n;i++){
		if(is[i]==0){
			p[++cnt]=i;
			phi[i]=i-1;//质数全沪指 
		}
		for(int j=1;j<=cnt;j++){
			if(i*p[j]>n) break;
			is[p[j]*i]=1;
			if(i%p[j]==0){
				phi[p[j]*i]=p[j]*phi[i];
				break;
			}
			else phi[p[j]*i]=(p[j]-1)*phi[i];
		}
	}
	ll ans=0;
	for(int i=1;i<=n;i++) ans+=phi[i];
	return ans;
}

int main() {
    cin>>n;
    cout<<solve();
    return 0;
}