算法板子：欧拉函数——求一个数的欧拉函数、线性时间内求1~n所有数的欧拉函数

目录

1. 欧拉函数

（1）概念

（2）性质

（3）计算公式

2. 求一个数的欧拉函数

（1）模拟过程

（2）代码 

3. 线性时间内求1~n所有数的欧拉函数——筛法求欧拉函数

（1）要点

（2）代码

1. 欧拉函数

（1）概念

给一个整数n，求n的欧拉函数就是求1~n中有几个数和n互质。互质就是两个整数除了1以外没有其他的公约数。

（2）性质

（3）计算公式

2. 求一个数的欧拉函数

（1）模拟过程

（2）代码 

#include <iostream>
using namespace std;// 求x这个数的欧拉函数
int phi(int x)
{// res代表1~x中与x互质的数的个数int res = x;// i从2枚举到根号xfor (int i = 2; i <= x / i; i ++ ){// 如果i是x的质因子if (x % i == 0){// 记得先除质因子再乘质因子减一; 先乘法可能会爆intres = res / i * (i - 1);while (x % i == 0) x /= i;}}// 如果最终x>1, 代表最终x也是原x的质因子; 所以就除质因子再乘质因子减一if (x > 1) res = res / x * (x - 1);return res;
}int main()
{int n;cin >> n;while (n --){int x;cin >> x;cout << phi(x) << endl;}return 0;
}

3. 线性时间内求1~n所有数的欧拉函数——筛法求欧拉函数

（1）要点

可以在线性的时间内求出1~n所有数的欧拉函数，时间复杂度比上一种更小，模版类似筛法求质数。

（2）代码

#include <iostream>
using namespace std;const int N = 1e6 + 10;
int n;// vis[i]代表i这个数是否是合数; vis[4]=1代表4这个数是合数, vis[3]=0代表3这个数是质数
// p[i]代表第1~n中i个质数的值; p[1]=2代表1~n中第1个质数是2
// cnt代表1~n中质数的个数
int vis[N], p[N], cnt;
// phi[i]代表i这个数的欧拉函数; phi[5]=4代表5这个数的欧拉函数为4(跟5互质的数有1,2,3,4)
int phi[N];// 求1~n所有数的欧拉函数
void get_phi(int n)
{// 特判1的欧拉函数phi[1] = 1;// 求2~n所有数的欧拉函数for (int i = 2; i <= n; i ++ ){// 如果i是质数, 记录在p数组中, 并且质数的欧拉函数是质数减一if (!vis[i]) p[ ++ cnt] = i, phi[i] = i - 1;// j从1开始枚举for (int j = 1; 1LL * i * p[j] <= n; j ++ ){// 记录i*p[j]是合数vis[i * p[j]] = 1;// 求i*p[j]的欧拉函数if (i % p[j] == 0) {phi[i * p[j]] = phi[i] * p[j];break;}else phi[i * p[j]] = phi[i] * (p[j] - 1);}}
}int main()
{cin >> n;// 得到1~n所有数的欧拉函数, 记录在phi数组中get_phi(n);long long res = 0;for (int i = 1; i <= n; i ++ ) res += phi[i];cout << res << endl;return 0;
}