欧拉系列
欧拉函数
欧拉函数 \(\varphi(n)\) 表示 \(1 \sim n\) 内与 \(n\) 互质的数的个数。
性质
- 欧拉函数是积性函数，特别的有 \(\varphi(2n) = \varphi(n)\) 。
- \(\sum_{d | n} \varphi(d) = n\) 。
- 证明：设 \(f(x)\) 表示 \(\gcd(k, n) = x (k \in [1, n])\) 的个数，则 \(n = \sum_{d | n} f(d) = \sum_{d | n} \varphi(\dfrac{n}{d}) = \sum_{d | n} \varphi(d)\) 。
- 当 \(n\) 为质数时， \(\varphi(n) = n - 1\) 。
- 若 \(n = p^k (p \in prime)\) ，则 \(\varphi(n) = p^k - p^{k - 1}\) 。
- 由唯一分解定理，设 \(n = \prod p_i^{k_i}\) ，则 \(\varphi(n) = n \times \prod \dfrac{p_i - 1}{p_i}\) ，证明考虑用积性函数性质即可。
- $n > 2 \rightarrow 2 | \varphi(n) $ ，证明考虑对称性即可。
- 对于 \(m, n \not = 0\) ，有 \(\varphi(mn) \varphi(\gcd(m, n)) = \varphi(m) \varphi(n) \gcd(m, n)\) 。
求法
求单个数的欧拉函数：
inline int euler_phi(int n) {
int phi = n;
for (int i = 2; i * i <= n; ++i)
if (!(n % i)) {
phi = phi / i * (i - 1);
while (!(n % i))
n /= i;
}
if (n > 1)
phi = phi / n * (n - 1);
return phi;
}
线性筛法：
inline void prework(int n) {
memset(isp, true, sizeof(isp));
isp[1] = false, phi[1] = 1;
for (int i = 2; i <= n; ++i) {
if (isp[i])
pri[++pcnt] = i, phi[i] = i - 1;
for (int j = 1; j <= pcnt && i * pri[j] <= n; ++j) {
isp[i * pri[j]] = false;
if (i % pri[j])
phi[i * pri[j]] = phi[pri[j]] * phi[i];
else {
phi[i * pri[j]] = pri[j] * phi[i];
break;
}
}
}
}
费马小定理
若 \(p\) 为质数且 \(\gcd(a, p) = 1\) ，则 \(a^{p - 1} \equiv 1 \pmod{p}\)
另一种形式：对于任意整数 \(a\) ，有 \(a^p \equiv a \pmod{p}\) 。
证明：考虑数学归纳法，显然 \(1^p \equiv 1 \pmod{p}\) 成立。假设 \(a^p \equiv a \pmod{p}\) 成立，则：
\[(a + 1)^p = a^p + \dbinom{p}{1} a^{p - 1} + \cdots + \dbinom{p}{p - 1} a + 1 \equiv a^p + 1 \equiv a + 1 \pmod{p} \]得证。
欧拉定理
欧拉定理：若 \(gcd(a, m) = 1\) ，则 \(a^{\varphi(m)} \equiv 1 \pmod{m}\) 。
实际上费马小定理就是欧拉定理 \(m \in prime\) 的特殊情况。
扩展欧拉定理
\[a^b \equiv \begin{cases} a^{b \bmod \varphi(m)}, &\gcd(a, m) = 1, \\ a^b, &\gcd(a, m \not = 1), b < \varphi(m), \\ a^{(b \bmod \varphi(m)) + \varphi(m)}, &\gcd(a, m) \not = 1, b \geq \varphi(m). \end{cases} \pmod{m} \]第二行意思是若 \(b < \varphi(m)\) 就不能降幂了。
欧拉反演
本质就是利用 \(n = \sum_{d | n} \varphi(d)\) 做一些变换。
如：
\[\gcd(i, j) = \sum_{d | \gcd(i, j)} \varphi(d) = \sum_{d | i} \sum_{d | j} \varphi(d) \]于是可以得到：
\[\sum_{i = 1}^n \gcd(i, n) = \sum_{i = 1}^n \sum_{d | n} \sum_{d | i} \varphi(d) = \sum_{d | n} \lfloor \dfrac{n}{d} \rfloor \varphi(d) \]应用
\[\begin{align} &\sum_{i = 1}^n \sum_{j = 1}^m \gcd(i, j) \\ =& \sum_{i = 1}^n \sum_{j = 1}^m \sum_{k | i} \sum_{k | j} \varphi(k) \\ =& \sum_{k = 1}^n \varphi(k) \sum_{i = 1}^n \sum_{j = 1}^m [k | i] [k | j] \\ =& \sum_{k = 1}^n \lfloor \dfrac{n}{k} \rfloor \lfloor \dfrac{m}{k} \rfloor \varphi(k) \end{align} \]求：
\[\sum_{i = 1}^n \sum_{j = 1}^n \gcd(i, j) \]\(n \leq 10^5\)
本题是 \(m = n\) 的特殊情况，\(O(n)\) 预处理， \(O(\sqrt{n})\) 查询即可。
标签：系列,gcd,dfrac,sum,varphi,欧拉,equiv From： https://www.cnblogs.com/wshcl/p/18354300/euler另解：设 \(f_k\) 表示 \(\gcd(i, j) = k\) 的个数，\(g_k\) 表示 \(k | \gcd(i, j)\) 的个数，显然 \(g_k = \sum f_{kd} = \lfloor \dfrac{n}{k} \rfloor^2\) ，故 \(f_k = \lfloor \dfrac{n}{k} \rfloor^2 - (f_{3k} + f_{3k} + \cdots)\)
复杂度为 \(O(n H(n))\) ，其中 \(H(n)\) 为调和级数。