[也许更好的阅读体验](https://www.cnblogs.com/ConanKID/p/number-theory.html)
---
## Part 1 扩展欧几里得（EXGCD）
裴蜀定理：关于 $x,y$ 的方程 $ax+by=c$ 有整数解，当且仅当 $\gcd(a,b)|c$。
证明略。
现在的问题是如何求出 $x,y$。
因为 $c$ 是 $\gcd(a,b)$ 的倍数，所以只需要求出 $ax+by=\gcd(a,b)$ 的解即可。
考虑使用归纳法。假设已经求出了两个数 $x_0,y_0$，使得 $b\cdot x_0+(a\bmod b)\cdot y_0=\gcd(a,b)$，我们尝试把 $x,y$ 用 $x_0,y_0$ 表示出来：
$\kern{110pts}\gcd(a,b)=b\cdot x_0+(a\bmod b)\cdot y_0$
$\kern{150pts}=b\cdot x_0+(a-\lfloor\frac{a}{b}\rfloor\cdot b)\cdot y_0$
$\kern{150pts}=a\cdot y_0+b\cdot(x_0-\lfloor\frac{a}{b}\rfloor\cdot y_0)$
因此可令 $x=y_0,y=x_0-\lfloor\frac{a}{b}\rfloor\cdot y_0$，即得到了原方程的一组解。
$x_0,y_0$ 也递归去求就好了。
发现 $a,b$ 在递归过程中的变化方式就是一个辗转相除的过程。这也是这个算法的得名原因。
```cpp
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {x = 1, y = 0; return a;}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
```
P.S.：这个函数的停止递归条件里，由于 $y$ 的系数为 $0$，所以无论把它设什么值都是对的。只是如果设 $114514$ 这种值有爆 $\operatorname{long\kern{4pts}long}$的风险。
扩展欧几里得算法可以用来解同余方程，即求出最小的正整数 $x$，使得 $ax\equiv b\pmod m$。易知这个同余式成立的充要条件是存在正整数 $y$，使得 $ax+my=b$。因此只需要用扩欧求 $x$ 就行了。
接下来看 [这道题](https://www.luogu.com.cn/problem/P1516)。
设两只青蛙碰面的时间为 $t$ 天，那么显然：
$$x+tm\equiv y+tn\pmod L$$
所以
$$t(m-n)\equiv y-x\pmod L$$
这个东西就是一个标准的同余方程形式了，可以用扩欧搞。需要注意的一点是得保证未知数的系数非负，即如果 $m<n$ 那么需要将方程两边同时取负。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int m, n, a, b, l;
int x, y;
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {x = 1, y = 0; return a;}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
signed main() {
cin >> a >> b >> m >> n >> l;
if (m < n) swap(m, n), swap(a, b);
int d = exgcd(m - n, l, x, y);
if ((b - a) % d != 0) {cout << "Impossible" << endl; return 0;}
x *= (b - a) / d, y *= (b - a) / d;
l /= d;
cout << (x % l + l) % l << endl;
return 0;
}
```
---
## Part 2 乘法逆元
定义：若 $ax\equiv 1\pmod b$，则称 $x$ 为 $a$ 在模 $b$ 意义下的乘法逆元，记作 $a^{-1}=x$。
求法：
1. 扩展欧几里得。上文已经提到过，不再赘述。
2. 费马小定理。若 $p$ 为质数且 $\gcd(a,p)=1$，则 $a^{p-1}\equiv1\pmod p$，因此 $a^{-1}=a^{p-2}$。
3. 线性递推，详见 [P3811](https://www.luogu.com.cn/problem/P3811)。我们让模数 $m$ 对 $a$ 做带余除法，设 $m=aq+r$，那么
$$aq\equiv -r\pmod m$$
因此
$$a\equiv -r\cdot q^{-1}\pmod m$$
两边同取逆元
$$a^{-1}\equiv -r^{-1}\cdot q\pmod m$$
于是我们就得到了递推公式：
$$a^{-1}=(-(m\bmod a)^{-1}\cdot\lfloor\frac{m}{a}\rfloor)\bmod m $$
我们知道除法运算在模意义下是不封闭的，因此在求 $\dfrac{a}{b}\bmod p$ 时并没有一个好的办法，但乘法逆元的引入解决了这一问题：我们可以将除以 $b$ 转化为乘上 $b$ 的逆元。于是解决一些题目变得方便了许多。
考虑 [这道题](https://www.luogu.com.cn/problem/P1593)。
首先将 $a$ 分解质因数，设 $a=\prod_{i=1}^n {c_i}^{p_i}$，那么 $a^b=\prod_{i=1}^n {c_i}^{b\cdot p_i}$。根据因数和定理，答案即为
$$\prod\limits_{i=1}^n (\sum\limits_{j=0}^{b\cdot p_i} {c_i}^{j})$$
再用一下等比数列求和，式子化为
$$\prod\limits_{i=1}^n\dfrac{{c_i}^{b\cdot p_i+1}-1}{c_i-1}$$
我们需要求这个东西对于 $9901$ 取模的结果。考虑用逆元将除以 $c_i-1$ 转化为乘上它的逆元，注意到 $9901$ 是个质数，所以直接用费马搞即可。
一个坑点是要特判 $c_i-1$ 不存在逆元的情况，即 $c_i\equiv 1\pmod {9901}$。此时显然 $\sum_{j=0}^{b\cdot p_i} {c_i}^{j}\equiv b\cdot p_i+1\pmod {9901}$。
于是就做完了。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a, b;
int p[1005], c[1005], cnt;
int ans = 1;
int power(int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p; b >>= 1;
}
return res % p;
}
int calc(int k) {
if (p[k] == 9901) return 1;
if (p[k] % 9901 == 1) return (c[k] + 1) % 9901;
int ans = (power(p[k], b * c[k] + 1, 9901) - 1) * power(p[k] - 1, 9899, 9901) % 9901;
return (ans + 9901) % 9901;
}
signed main() {
cin >> a >> b;
int x = 2;
while (a != 1) {
if (a % x == 0) {
p[++cnt] = x;
while (a % x == 0) c[cnt]++, a /= x;
}
x++;
}
for (int i = 1; i <= cnt; i++)
ans = ans * calc(i) % 9901;
cout << ans << endl;
return 0;
}
```
---
## Part 3 中国剩余定理（CRT）
中国剩余定理的基本形式如下：
现有 $n$ 个关于 $x$ 的方程，形如 $x\equiv a_i\pmod{m_i}$，且所有的 $m$ 两两互质，令 $M=m_1m_2\cdots m_n$，则 $x$ 在模 $M$ 意义下有唯一解。
扩展中国剩余定理（EXCRT），在原定理的基础上去除了所有的 $m$ 都互质这一条件，需要我们求出方程的一个解 $x$。
考虑归纳法。设前 $k-1$ 个方程的一个特解为 $x$，通解为 $x+aM$，其中 $M=\operatorname{lcm}(m_1,m_2\cdots m_{k-1})$，现在需要求一个整数 $t$，使得 $x+tM\equiv a_k\pmod {m_k}$。显然这个东西可以用 EXGCD 搞。
然后就没了。
以下是 [P4777](https://www.luogu.com.cn/problem/P4777) 的代码。
```cpp
#include<bits/stdc++.h>
#define lcm nmsl
#define int __int128
using namespace std;
int n;
int a[100005], m[100005];
int pm = 1;
int ans, lcm;
short tnnd[15], len;
int read() {
int x = 0, f = 1; char c = getchar();
while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
while (isdigit(c)) {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
return x * f;
}
void print(int x) {
len = 0;
while (x) tnnd[++len] = x % 10, x /= 10;
for (int i = len; i >= 1; i--) cout << tnnd[i];
cout << endl;
}
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {x = 1, y = 0; return a;}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
void get(int k) {
int x, y;
a[k] = (a[k] - ans % m[k] + m[k]) % m[k];
int d = exgcd(lcm, m[k], x, y);
ans += x * a[k] / d % m[k] * lcm; lcm = lcm / d * m[k]; ans = (ans % lcm + lcm) % lcm;
}
signed main() {
n = read();
for (int i = 1; i <= n; i++)
m[i] = read(), a[i] = read();
ans = a[1], lcm = m[1];
for (int i = 2; i <= n; i++)
get(i);
print((ans % lcm + lcm) % lcm);
return 0;
}
```
由于中间运算的结果可能会爆 $\operatorname{long\kern{4pts}long}$，所以可以考虑使用快速乘。我比较懒直接用了 int128。
---
## Part 4 欧拉函数及扩展欧拉定理
定义：对于正整数 $n$，它的欧拉函数为不超过 $n$ 且与其互质的正整数数量，记为 $\varphi(n)$。
考虑如何计算 $\varphi(n)$。将 $n$ 分解质因数：$n=\prod_{i=1}^m {c_i}^{p_i}$，那么显然有
$$\varphi(n)=n\cdot \prod\limits_{i=1}^m\dfrac{c_i-1}{c_i}$$
网上证明一大堆这里就不写了反正也不太重要。
这个式子就是欧拉公式。这样我们求 $\varphi(n)$ 只需要将其分解质因数即可，可以做到 $O(\sqrt n)$ 的复杂度。
另外如果要求 $1-n$ 中所有数的欧拉函数，可以考虑在筛质数的过程中顺便处理一下。时间复杂度 $O(n\log\log n)$ 或 $O(n)$，依实现方式而定。
欧拉定理：若 $\gcd(a,n)=1$，则 $a^{\varphi(n)}\equiv 1\pmod n$。
证明可以用既约剩余系。这里不写了。
扩展欧拉定理：若 $b\ge \varphi(n)$，那么 $a^b\equiv a^{b\bmod \varphi(n)+\varphi(n)}\pmod n$。证明略。
这个东西其实是相当有用的。注意到当 $b$ 特别大时，求 $a^b\bmod n$ 非常困难，以至于不仅要写高精，而且快速幂还会 T。但有了扩展欧拉定理我们就可以让 $b$ 先对 $\varphi(n)$ 取模再去求快速幂，高精不用写并且稳稳地不会超时。
以下是 [P5091](https://www.luogu.com.cn/problem/P5091) 的代码。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a, b, p;
int phi;
int getphi(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 ans;
}
int power(int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p; b >>= 1;
}
return res % p;
}
signed main() {
cin >> a >> p; phi = getphi(p);
int x = 0, f = 0; char c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) {
x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();
if (x >= phi) x %= phi, f = 1;
}
b = x + f * phi;
cout << power(a, b, p) << endl;
return 0;
}
```
至此我们对所有基本运算（加减乘除以及乘方）的取模都有了一个较好的处理方式。
~~所以接下来的数论肯定也会恶心起来。~~
---
一些题目：
- [P1082 [NOIP2012 提高组] 同余方程](https://www.luogu.com.cn/problem/P1082)
- [P5656 【模板】二元一次不定方程 (exgcd)](https://www.luogu.com.cn/problem/P5656)
- [P3811 【模板】乘法逆元](https://www.luogu.com.cn/problem/P3811)
- [P4942 小凯的数字](https://www.luogu.com.cn/problem/P4942)
- [P2054 [AHOI2005]洗牌](https://www.luogu.com.cn/problem/P2054)
- [P4139 上帝与集合的正确用法](https://www.luogu.com.cn/problem/P4139)