定义
欧拉函数，即 \(\varphi(n)\)，表示的是 \([1, n]\) 内与 \(n\) 互质的数的个数，如 \(\varphi(1) = 1\)。
若 \(n\) 是质数，显然 \(\varphi(n) = n - 1\)。
性质
-
欧拉函数是积性函数。
若 \(\gcd(a, b) = 1\)，则 \(\varphi(a \times b) = \varphi(a) \times \varphi(b)\)。
更特殊地有，当 \(n\) 是奇数时，\(\varphi(2n) = \varphi(n)\)。
-
\(n = \sum\limits_{d | n} \varphi(d)\)。
记 \(f(x) = \sum\limits_{i = 1}^n[\gcd(i, n) = x]\)，则有 \(n = \sum\limits_{i = 1}^n f(i)\)。
若 \(\gcd(k, n) = d\)，则 \(\gcd(\dfrac kd, \dfrac nd) = 1\)，故 \(f(d) = \varphi(\dfrac nd)\)。
综上有：\(n = \sum\limits_{d | n}\varphi(\dfrac nd) = \sum\limits_{d | n}\varphi(d)\)。
-
若 \(n = p^k\)，其中 \(p\) 是质数，则 \(\varphi(n) = p^k - p^{k - 1}\)。
由上一条性质得：\(p^k = \sum\limits_{i = 0}^k \varphi(p^i)\)，于是显然后 \(p^k - p^{k - 1} = \varphi(p^k)\)。
-
设 \(n = \prod\limits_{i = 1}^sp_i^{k_i}\)，其中 \(p_i\) 是质数（即将 \(n\) 质因数分解），有 \(\varphi(n) = n \times \prod\limits_{i = 1}^s\dfrac{p_i - 1}{p_i}\)。
由第一条性质得：\(\varphi(n) = \prod\limits_{i = 1}^s \varphi(p_i^{k_i})\)。
由第三条性质得：\(\varphi(p_i^{k_i}) = p_i^{k_i} - p_i^{k_i - 1} = p_i^{k_i}(1 - \dfrac1{p_i})\)。
综上有：\(\varphi(n) = \prod\limits_{i = 1}^sp_i^{k_i} \times \prod\limits_{i = 1}^s\dfrac{p_i - 1}{p_i} = n \times \prod\limits_{i = 1}^s\dfrac{p_i - 1}{p_i}\)。
实现
如果是求单个数的欧拉函数，直接质因数分解求就好了，时间复杂度最坏是 \(\mathcal O(\sqrt n)\)，一般很难跑满，得是质数的平方数才能卡到 \(\mathcal O(\sqrt n)\)，实际跑更像 \(\mathcal O(\log n)\)。
int phi(int n) {
int ans = n;
for (int i = 2; i * i <= n; i++) if (n % i == 0) {
ans = ans / i * (i - 1);
while (n % i == 0) n /= i;
}
if (n > 1) ans = ans / n * (n - 1);
return res;
}
实际上欧拉函数也可以通过欧拉筛求得。
在欧拉筛中，每个合数都会被它最小的质因数筛掉，设当前合数为 \(n\)，其最小质因数为 \(p\)，记 \(n' = \dfrac np\)，分讨：
\[\varphi(n) = \begin{cases}p \times \varphi(n') & p | n' \\ \varphi(p) \times \varphi(n') & \rm{otherwise} \end{cases} \]第二种情况是好理解的，显然此时 \(\gcd(p, n') = 1\)，然后就可以用积性函数的性质了，但第一种情况是为什么呢？
若 \(p | n'\)，则说明 \(n\) 和 \(n'\) 的质因数构成的集合 \(S\) 是相同的，此时有：
\[\begin{aligned} \varphi(n) &= p \times n' \times \prod_{i = 1}^sp_i^{k_i} \\ &= p \times (n' \times \prod_{i = 1}^sp_i^{k_i}) \\ &= p \times \varphi(n') \end{aligned} \]欧拉筛求 \([1, n]\) 内欧拉函数的时间复杂度是 \(\mathcal O(n)\)。
int phi[N];
bool vis[N];
vector<int> prime;
void getphi(int n) {
phi[1] = 1;
for (int i = 2; i <= n; i++) {
if (!vis[i]) prime.emplace_back(i), phi[i] = i - 1;
for (int p : prime) {
if (p * i > n) break;
vis[p * i] = 1;
if (i % p) phi[p * i] = phi[p] * phi[i];
else {phi[p * i] = p * phi[i]; break;}
}
}
}
欧拉定理
若 \(\gcd(a, m) = 1\)，则 \(a^{\varphi(m)} \equiv 1 \pmod m\)。
当 \(m\) 是质数时，\(\varphi(m) = m - 1\)，有 \(a^{m - 1} \equiv 1 \pmod m\)，这就是 费马小定理，它是欧拉定理的一种特殊情况。
扩展欧拉定理
\[a^b = \begin{cases}a^{b \bmod \varphi(p)} & \gcd(a, p) = 1 \\ a^b & \gcd(a, p) \ne 1, b \le \varphi(p) \\ a^{b \bmod \varphi(p) + \varphi(p)} & \gcd(a, p) \ne 1, b > \varphi(p) \end{cases} \pmod p \]例题
P2158 [SDOI2008] 仪仗队
给定一个 \(n \times n\) 的方阵，方阵上的点会互相遮挡，问在方阵左下角能看到的点数。\(n \le 4 \times 10^4\)。
把行和列都从 \(0 \sim N - 1\) 编号，然后所求转化为：
\[2 + \sum_{i = 1}^{n - 1}\sum_{j = 1}^{n - 1}[\gcd(i, j) = 1] \]套上欧拉函数，得：
\[1 + 2\sum_{i = 1}^{n - 1} \varphi(i) \]要特判 \(n = 1\) 的情况。
时间复杂度 \(\mathcal O(n)\)。
P2155 [SDOI2008] 沙拉公主的困惑
求 \([1, n!]\) 中与 \(m!\) 互质的数的数量，对 \(998244353\) 取模。\(m \le n \le 10^7\)。
答案是 \(\sum\limits_{i = 1}^{n!}[\gcd(i, m!) = 1]\)，由 \(\gcd(a, b) = \gcd(b, a \bmod b)\) 得 \(\gcd(i + km!, m!) = \gcd(m!, i)\)，故答案转化为 \(\dfrac{n!}{m!}\varphi(m!)\)。
考虑递推地求解 \(\varphi(n!)\)。
\[\varphi(n!) = \begin{cases}\varphi[(n - 1)!] \times (n - 1) & n \in \rm{prime} \\ \varphi[(n - 1)!] \times n & \rm{otherwise} \end{cases} \]然后注意 \(n, m\) 可能大于等于模数的情况即可。
时间复杂度 \(\mathcal O(n)\)。
标签：gcd,limits,sum,varphi,times,利器,欧拉 From： https://www.cnblogs.com/chy12321/p/18002783