Day13 学习资料

[李毅皓]

一. 欧拉筛

代码：

for (int i = 2; i <= n; i++) {
     if (!vis[i]) p[++cnt] = i;
	 for (int j = 1; i * p[j] <= n; j++) {
		vis[i * p[j]] = 1;
		if (i % p[j] == 0) break;
	 }
}

二. 线性推逆元

代码：

inv[1] = 1;
for (int i = 2; i <= n; i++) {
	inv[i] = p - (p / i) * inv[p % i] % p;
}

三. 费马小定理

内容：若 p 为素数，gcd(a, p) = 1，则 a^{p - 1} \equiv 1 \pmod{p}。

另一个形式：对于任意整数 a，有 a^p \equiv a \pmod{p}。