欧拉函数(模板)
欧拉函数:欧拉函数是小于或等于 n 的正整数中与 n 互质的数的数目((1)=1),
记为(n)。
欧拉函数的通式:(n)=
欧拉函数的性质:n 的因子的欧拉函数加起来等于 n 。
1.求正整数 n 的欧拉函数:
int euler(int n){int ret=n;for(int i=2;i*i<=n;i++){if(n%i==0){ret-=ret/i;while(n%i==0) n/=i;}}if(n>1) ret-=ret/n;return ret;
}
2.欧拉函数的线性求法:
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
int vis[maxn],prime[maxn],phi[maxn];
signed main(){int n;cin >> n;int cnt=0;phi[1]=1;for(int i=2;i<=n;i++){if(!vis[i]) prime[++cnt]=i,phi[i]=i-1;for(int j=1;j<=cnt && i*prime[j]<=n;j++){vis[i*prime[j]]=1;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}phi[i*prime[j]]=phi[i]*(prime[j]-1);}}cout << phi[n] << endl;return 0;
}