特别的,当n=1时,欧拉函数值为1。当n为质数时,欧拉函数的值为n-1。
欧拉函数直接求法:
模板:https://www.acwing.com/problem/content/875/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| #include<bits/stdc++.h> using namespace std; int n; int main(void) { scanf("%d",&n); while(n--) { int x; scanf("%d",&x); int res=x; for(int i=2;i<=x/i;i++) { if(x%i==0) { res = (res/i)*(i-1); while(x%i==0)x/=i; } } if(x>1) res =(res/x)*(x-1); printf("%d\n",res); } }
|
筛法求欧拉函数:
模板:https://www.acwing.com/problem/content/876/
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
| #include<bits/stdc++.h> using namespace std; const int N =1e6+5; int prime[N]; bool st[N]; int phi[N]; int n; int cnt; long long getol(int n) { phi[1]=1; for(int i=2;i<=n;i++) { if(!st[i]) { prime[cnt++]=i; phi[i] = i-1; } for(int j=0;prime[j]<=n/i;j++) { st[prime[j]*i] =true; if(i%prime[j]==0) { phi[i*prime[j]] =prime[j]*phi[i]; break; } phi[i*prime[j]] = (prime[j]-1)*phi[i]; } } long long ans=0; for(int i=1;i<=n;i++) { ans+= phi[i]; } return ans; } int main(void) { scanf("%d",&n); printf("%lld",getol(n)); }
|