欧拉函数
欧拉函数（写作 \(\varphi(x)\)），表示 \(i\in[1,x] 且 \gcd(i,x)=1\) 的 \(i\) 的数量。
乍一看好像很难求，但我们先考虑最简单的情况，即 \(x\in \mathbb{P}\) （\(\mathbb{P}\) 表示质数集） 的情况。
首先很容易看出 \(\varphi(x)=x-1\)，因为 \(x\in \mathbb{P}\)，所以 \(\forall i \in [1,x-1]\) 都有 \(\gcd (i,x)=1\)。
接着，我们可以想到 \(\varphi (x^2)=x^2-x\)，因为总共 \(x^2\) 个数，\(x\) 的倍数都不合法，总共 \(\frac{x^2}{x}=x\) 个 \(x\) 的倍数。
继续，\(\varphi (x^3)=x^3-x^2\)，因为总共 \(x^3\) 个数，\(x\) 的倍数都不合法，总共 \(\frac{x^3}{x}=x^2\) 个 \(x\) 的倍数。
$\vdots $
最终，我们可以得到 \(\forall k \ge 1,\varphi (x^k)=x^k-x^{k-1}=(x-1)x^{k-1}\)。
接着，我们来考虑这个问题：当 \(\gcd(a,b)=1\) 时，\(\varphi(a\cdot b)=\varphi(a)\cdot\varphi(b)\)。（即证欧拉函数是积性函数）
我们来感性理解一下，对于所有 \(x\le a且\gcd(x,a)=1\) 的数 \(x\) 和 \(y \le b 且 \gcd(y,b)=1\) 的 \(y\)，那么 \(\gcd(x\cdot y,a\cdot b)=1\)，因为 \(x\) 的质因子 \(a\) 都没有，\(y\) 的质因子 \(b\) 也都没有，所以相乘后仍然没有。即每个 \(x\cdot y\) 为一个合法的数，所以 \(\varphi(a\cdot b)=\varphi (a)\cdot \varphi(b)\)。
接下来我们就可以求解 \(\varphi(x)\) 了。
方法1
这种方法可以 \(O(\sqrt x)\) 求出一个单独的 \(\varphi (x)\)。
首先我们可以把 \(x\) 拆成这样：\(x=p_1^{e_1}\cdot p_2^{e_2}\cdot p_3^{e_3}\cdot \cdots\)。
接着，通过 \(\varphi(a\cdot b)=\varphi(a)\cdot \varphi(b)\)，我们可以将式子变成 \(\varphi(x)=\varphi (p_1^{e_1})\cdot \varphi(p_2^{e_2})\cdot \varphi(p_3^{e_3})\cdot \cdots\)
最终我们就可以得到 \(\varphi(x)=(p_1-1)\cdot p_1^{e_1-1}\cdot (p_2-1)\cdot p_2^{e_2-1}\cdot (p_3-1)\cdot p_3^{e_3-1}\cdot \cdots\)。而这段直接用分解质因数求解即可。
代码
int phi(int x) {
int res = 1;
for(int i = 2; i * i <= x; ++i) {
if(x % i == 0) {
x /= i, res *= i - 1;
for(; x % i == 0; x /= i, res *= i) {
}
}
}
return res * (x > 1 ? x - 1 : 1);
}
phi(x);
方法2
这种方法可以 \(O(N)\) 求出 \(\forall x\in [1,N]\) 的 \(\varphi(x)\)，并且欧拉筛及其相似。
首先我们可以直接在筛出质数时求解，并且可以找到一个数的最小质因子，而这种方法就是通过最小质因子求解的。
当枚举到质数 \(p\)，倍数为 \(i\)：
- 如果 \(\gcd(p,i)=1\)，那么 \(\varphi (p\cdot i)=\varphi(i)\cdot(p-1)\)。
- 否则，\(\varphi(p \cdot i)=\varphi(i)\cdot p\)，因为相当于让 \(p\) 的指数加一，所以答案乘以 \(p\)。
代码
int phi[MAXN];
vector<int> prime;
void C(int x) {
phi[1] = 1;
for(int i = 2; i <= x; ++i) {
if(!phi[i]) {
phi[i] = i - 1;
prime.push_back(i);
}
for(int p : prime) {
if(i * p > x) {
break;
}
if(i % p == 0) {
phi[i * p] = phi[i] * p;
break;
}
phi[i * p] = phi[i] * phi[p];
}
}
}
C(n);
整除分块
整除分块，就是 \(O(\sqrt k)\) 求解类似于 \(\sum \limits_{i=1}^{N} \lfloor\frac{k}{i}\rfloor\) 的式子。
整除分块的主要思想就是枚举 \(\lfloor\frac{k}{i}\rfloor\) 的值，因为我们可以证明值的数量是 \(O(\sqrt k)\) 级别的：
- 当 \(i \le \sqrt k\) 时，\(\lfloor \frac{k}{i} \rfloor\) 的数量很明显 \(\le \sqrt k\)。
- 当 \(i > \sqrt k\) 时，\(\lfloor \frac{k}{i} \rfloor \le \sqrt k\)，即 \(\lfloor \frac{k}{i} \rfloor\) 的数量 \(\le \sqrt k\)。
所以总共是 \(O(\sqrt k)\) 级别的。
假设我们知道一个值出现的最早位置为 \(l\)，那么怎么求最后一个位置 \(r\) 呢？
\[\begin{array}{l} \lfloor \frac{k}{l}\rfloor=\lfloor \frac{k}{r}\rfloor\\ \lfloor \frac{k}{l}\rfloor \cdot r \le k\\ r \le \frac{k}{\lfloor \frac{k}{l}\rfloor},即r=\lfloor\frac{k}{\lfloor \frac{k}{l}\rfloor}\rfloor \end{array} \]代码
int ans;
for(int l = 1, r = 1; l <= min(k, n); l = r + 1) {
r = min(n, k / (k / l));
ans += (k / l) * (r - l + 1);
}
扩展欧几里得
扩展欧几里得 \(O(\sqrt{\min(a,b)})\) 求出 \(ax+by=c\)（\(\gcd(a,b) | c\)）的一组整数解。
直接开推（这里只考虑 \(c=\gcd(a,b)\) 的情况，其余情况将答案 \(\times k\) 即可）：
\[\begin{array}{l} ax+by=\gcd(a,b)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \Downarrow\\ b \cdot x' + (a-\lfloor\frac{a}{b}\rfloor \cdot b)\cdot y'=\gcd(b,a \bmod b)\\ b\cdot x'+a\cdot y'-\lfloor \frac{a}{b} \rfloor \cdot by'=\gcd(b,a \bmod b)\\ a\cdot y'+b\cdot (x'-\lfloor \frac{a}{b} \rfloor\cdot y')=\gcd(b,a \bmod b)\\ \therefore ax+by=\gcd(a,b)=a\cdot y'+b\cdot (x'-\lfloor \frac{a}{b} \rfloor\cdot y')\\ \therefore 当\begin{cases}x=y'\\y=(x'-\lfloor \frac{a}{b} \rfloor \cdot y')\end{cases} 时是一组合法的解。 \end{array} \]只需按照上述方法不断操作直到 \(b=0\) 时即可。（当 \(b=0\) 时的一组解解为 \(\begin{cases}x=1\\y=0\end{cases}\)）
代码
using pii = pair<int, int>;
pii exgcd(int a, int b) {
if(!b) {
return {1, 0};
}
auto [x, y] = exgcd(b, a % b);
return {y, x - a / b * y};
}