第一行——咕咕咕。
第二行感谢ryc师哥。
欧拉函数：用于求1~n-1中与n互质的数的个数。
各种性质（用ph[n]表示与n欧拉函数值）：
1.n为素数，ph[n] = n-1
2.n>2，所有ph[n]的值均为偶数
3.任意n,m互质，ph[n*m] = ph[n]*ph[m]（积性函数）
4.任意n,m，gcd(n,m)=d，ph[n*m] = ph[n]*ph[m]/ph[d]*d
以上所有性质证明过程略（想知道证明过程欢迎自行百度）（主要是我觉得我讲不明白）（毕竟自己都不太明白）（等我愿意写证明过程再说吧）
本代码以SDNU1287为例。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define maxn 1000005 using namespace std; long long p[maxn]; long long ph[maxn]; bool vis[maxn] = {0}; int tot=0; void eul() { ph[0] = 0; ph[1] = 1; vis[0] = 1; vis[1] = 1; for(int i = 2; i <= maxn; ++i) { if(!vis[i]) { vis[i] = 1; p[tot++] = i; ph[i] = i-1;//性质1 } for(int j = 0; j < tot; ++j) { if(i*p[j]>maxn) break; vis[i*p[j]] = 1; if(i%p[j] == 0) break; } } } void euler() { for(int i = 2; i <= maxn; ++i) { for(int j = 0; j < tot; ++j) { if(i*p[j] > maxn) break; else { vis[i*p[j]] = 1; if(i%p[j] == 0) { ph[i*p[j]] = ph[i]*p[j];//性质4，i与p[j]的最大公约数即为质数本身 } else ph[i*p[j]] = ph[i]*(p[j]-1);//性质3+性质1，与质数的公约数不是该质数即为1 } } } } int main() { eul(); euler(); int t; scanf("%d",&t); for(int i = 0; i < t; ++i) { int n; scanf("%d",&n); printf("%lld\n",ph[n]); } return 0; }下附其他练习
SPOJETF
//后期可能会再更新几个欧拉函数的练习
欢迎指出错误qwq
