include<bits/stdc++.h> usingnamespace std; typedeflong long ll; ll phi[100001]; constint N=100000; voidinit() { ????for(inti=1;i<=N;i++) ????phi[i]=i; ????for(inti=2;i<=N;i++) ????{ ????????if(i==phi[i])//判斷i是不是質數（如果i不是質數那么在到達i之前phi[i]就會發生改變了） ????????for(intj=i;j<=N;j+=i) ????????phi[j]=(phi[j])/i*(i-1); ????} } intmain() { ????intn; ????init(); ????while(~scanf("%d",&n)) ????{ ????????printf("%d\n",phi[n]); ????} ????? }

總結

以上是生活随笔為你收集整理的欧拉函数的求法（线性筛法？）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。