什么是逆元？

若 $ax \equiv 1 \pmod b$，则称 $x$ 是 $a$ 关于模 $b$ 的逆元，常记做 $a^{-1}$。

上式等价于 $ax + by = 1$，因此，一种求逆元的方法就是利用扩欧解方程 $ax + by = 1$。

显然，逆元不一定存在：其存在的充要条件为 $(a, b) = 1$。

推论：$p$ 是质数，$p$ 不整除 $a$，则 $a$ 模 $p$ 的逆元存在。

欧几里得算法

又称辗转相除法，迭代求两数 gcd。

由 $(a, b) = (a, ka + b)$ 的性质，$\gcd(a, b) = \gcd(b, a\bmod b)$。容易证明这么做的复杂度是 $O(\log n)$。

注意：$\gcd(0, a) = a$。

整除分块

与其说整除分块是一种算法，不如说它是一个技巧。有时我们需要计算这样的式子：

$$
\sum_{i=1}^n f(i)\lfloor\frac{n}{i}\rfloor
$$

根据经验，我们发现 $\lfloor\frac{n}{i}\rfloor$ 只有 $O(\sqrt n)$ 种取值。对于每种取值，$i$ 都会有一个连续的范围。假设函数 $f$ 的前缀和可以预处理后快速求出，那么我们可以枚举 $\lfloor\frac{n}{i}\rfloor$ 的所有取值，并和 $f$ 的连续一段的和相乘。具体可以见代码：

1
2
3
4
5
6
7

// s[i] 为函数 f(i) 的前缀和 
int ans = 0;
for(int i=1, j; i<=n; i=j+1) {
    j = n/(n/i);
    ans += (s[j]-s[i-1])*(n/i);
}
printf("%d\n", ans);