【算法学习笔记】32：筛法求解欧拉函数
上节学习的是求一个数 n n n的欧拉函数，由于用的试除法，所以时间复杂度是 O ( n ) O(\sqrt{n}) O(n )，如果要求 m m m个数的欧拉函数，那么就会花 O ( m n ) O(m \sqrt{n}) O(mn )的时间。如果是求一连一批数的欧拉函数，可以用筛法进行优化。筛法求欧拉函数原理
在线性筛求质数时可以顺便把每个数的欧拉函数筛出来。根据线性筛过程，一个数要么是质数被pick出来，要么是合数被筛掉，一共有如许三个地方：
[*]从筛子（st数组）里发现 i i i是一个质数
[*]合数 p r i m e s [ j ] ∗ i primes * i primes∗i被筛掉，此中质数 p r i m e s [ j ] primes primes同时也是 i i i的质因子（按照线性筛，也肯定是最小质因子）
[*]合数 p r i m e s [ j ] ∗ i primes * i primes∗i被筛掉，此中质数 p r i m e s [ j ] primes primes不是 i i i的质因子（仅仅是 p r i m e s [ j ] ∗ i primes * i primes∗i的最小质因子）
三种环境合起来就不多不少地包罗了从 1 1 1到 n n n的所有数字。
[*]对于环境1，质数 i i i的欧拉函数根据定义就是除了 i i i之外的那 i − 1 i - 1 i−1个数，由于它们肯定都和 i i i互质，所以 ϕ ( i ) = i − 1 \phi(i) = i - 1 ϕ(i)=i−1
[*]对于环境2，由于 p r i m e s [ j ] primes primes也是 i i i的质因子，根据欧拉公式，除了第一项外剩下那些用1减的项，都只和质因子有关，和质因子的指数无关，因此相比 ϕ ( i ) \phi(i) ϕ(i)， ϕ ( p r i m e s [ j ] ∗ i ) \phi(primes * i) ϕ(primes∗i)只有第一项从 i i i酿成了 p r i m e s [ j ] ∗ i primes * i primes∗i
[*]对于环境3，由于 p r i m e s [ j ] primes primes是一个质数而且和 i i i互质，因此 ϕ ( p r i m e s [ j ] ∗ i ) \phi(primes * i) ϕ(primes∗i)的公式里，除了第一项要酿成 p r i m e s [ j ] ∗ i primes * i primes∗i，还由于添加了一个新的质数 p r i m e s [ j ] primes primes所以要乘以一个 1 − 1 p r i m e s [ j ] 1 - \frac{1}{primes} 1−primes1，所以总共要乘以 p r i m e s [ j ] − 1 primes - 1 primes−1
例题：AcWing 874. 筛法求欧拉函数
只要使用线性筛的模板和上面的结论，在三个地方填空即可。
#include <iostream>
using namespace std;
typedef unsigned long long ULL;
const int N = 1e6 + 10;
int primes, cnt;
bool st;
int eulars;
int main() {
int n; cin >> n;
eulars = 1;
for (int i = 2; i <= n; i ++ ) {
if (!st) {
primes = i;
// i是质数，从1到i-1都和i互质
eulars = i - 1;
}
for (int j = 0; primes * i <= n; j ++ ) {
st * i] = true;
if (i % primes == 0) {
// primes是i的质因子，欧拉公式里只要变第一项
eulars * i] = eulars * primes;
break;
}
// primes不是i的质因子，欧拉公式里要变第一项和(1-1/primes)那项
eulars * i] = eulars * (primes - 1);
}
}
ULL res = 0;
for (int i = 1; i <= n; i ++ ) {
res += eulars;
}
cout << res << endl;
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]