欧拉函数

欧拉函数其实我接触挺久了，一开始就是为了做pta的题刷分才学的，，，

后来发现，woc这玩意儿还挺有深度？？？？

这是我一开始的笔记，还挺潦草：

 我自己也看了老半天才看明白我之前写的什么鬼玩意儿。。。。。。

重开。。。

欧拉函数（Euler's totient function），即φ(n)，表示的是小于等于n和n互质的数的个数。

如果是素数，那么φ(n)=n-1，费马小定理那边就和这个关系很大

很好！！除了第一条，其他我都晕！！！！！

 1 int euler_phi(int n) {
 2   int ans = n;
 3   for (int i = 2; i * i <= n; i++)
 4     if (n % i == 0) {
 5       ans = ans / i * (i - 1);
 6       while (n % i == 0) n /= i;
 7     }
 8   if (n > 1) ans = ans / n * (n - 1);
 9   return ans;
10 }

先附上代码，太晚了，我要玩手机娱乐！！！！！！！！不能在学了！！！！！！之后再来复习吧啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊！！！！！！！！！！