【模板】欧拉函数

#include<cstdio> const int N=1e5+10; int phi[N]; void phi_table(int n)//1~n中所有数的欧拉phi值 { for(int i=2;i<=n;i++)phi[i]=0; phi[1]=1; for(int i=2;i<=n;i++) if(!phi[i]) for(int j=i;j<=n;j+=i) { if(!phi[j])phi[j]=j; phi[j]=phi[j]/i*(i-1); } } int euler(int x)//phi(x) { int ans=x; for(int i=2;i*i<=x;i++) if(x%i==0) { ans=ans/i*(i-1); while(x%i==0)x/=i; } if(x>1)ans=ans*x/(x-1); return ans; } int main() { return 0; }