欧拉函数

欧拉函数 1.欧拉函数 欧拉函数定义：1~n中与n互质的数的个数，例$φ(6) = 2$ 如果 $N = p1^{α1}p2^{α2}….*pn^{αn}$ 则有公式：$φ(N) = N*(1-\frac{1}{p1})(1-\frac{1}{p2})…(1-\frac{1}{pn})$； 时间复杂度：$O(n) = \sqrt{n}$ 2.AcWing873.欧拉函数对于每一个数字，分别从定义出发求其欧拉函数： 12345678910111213141516171819202122#include<iostream>using namespace std;int main() { int m; cin >> m; while (m--) { int num; cin >> num; int res = num;//最后结果 //1.分解质因数 for (int i = 2; i <= num / i; ++i) { if (num % i == 0) { /* i为num的一个因子 */ res = res / i * (i - 1);//res = res * (1 - 1/i);公式内容 while (num % i == 0) num /= i; } } //2.说明num有一个大于1的质因数 if (num > 1) res = res / num * (num - 1); cout << res << endl; } return 0;} 注意：在 res = res / num * (num - 1)中, 不能写成 res = res * (num - 1) / num;顺序不可颠倒 3.AcWing874.筛法求欧拉函数如果需要求出1~N中，每一个数字的欧拉函数，这时再使用公式法 ...