有以下的两条性质:
- if(gcd(i, prime[j]) == 1)
- phi[i * prime[j]] = phi[i] * phi[prime[j]];
- // 因为是积性函数. phi[prime[j]] 其实就是 prime[j]-1.
- else
- phi[i * prime[j]] = phi[i] * prime[j];
所以, 可以模仿埃氏筛的方法, 来进行递推, 顺便同时求出素数表.
- F(i, 1, n) phi[i] = i; // 相当于 not_prime[] 的作用
- F(i, 1, n) {
- if(phi[i] == i) phi[i] = i - 1, prime[++cnt] = i;
- F(j, 1, cnt) {
- if(i % prime[j] == 0) // 等价于 gcd(i, prime[j]) != 1
- phi[i * prime[j]] = phi[i] * phi[prime[j]];
- else
- phi[i * prime[j]] = phi[i] * prime[j];
- }
- }
而如果想要像埃氏筛优化成欧拉筛的方式一样, 把这个优化成线性的, 同样只需要加一行.
- F(i, 1, n) phi[i] = i;
- F(i, 1, n) {
- if(phi[i] == i) phi[i] = i - 1, prime[++cnt] = i;
- F(j, 1, cnt) {
- if(i % prime[j] == 0) {
- phi[i * prime[j]] = phi[i] * phi[prime[j]];
- break; // 这里加了一行
- }
- else
- phi[i * prime[j]] = phi[i] * prime[j];
- }
- }
递推求 phi[] 的问题就这样解决了!
来源: http://www.bubuko.com/infodetail-3207609.html