数论——求 phi

本文主要是介绍数论——求 phi，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$\phi$

1. $\phi$的定义

$\phi (n)$: 欧拉函数，费马小定理的扩展，求的是在[1, n]中，有多少个正整数和 n 互质

费马小定理只能用于质数，欧拉函数可以用于任何数(逆元)

2. 求$\phi$

暴力，利用$\phi$的性质

#include <algorithm>#define gcd __gcd // 还没有学gcd怎么用，不准自己写// 某些编译器可能不让用，就复制一下题解
#define int long longint phi(int x)
{int cnt = 0;for(int i = 1; i <= x; i ++){if(gcd(i, x) == 1) cnt ++;}return cnt;
}

太慢！时间复杂度$O(N\log N)$

怎么优化呢？

小茗优化

显然，在[1, N]中和N互质的正整数，就是和N没有相同的质因子的数

一个质因子就是质数，显然$\phi (N)=N-1$

考虑两个质因子的情况，设质因子分别为p, q

那么$1\to N$中，p的倍数有 N p \frac{N}{p}

这篇关于数论——求 phi的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---