1. 相关定理

• 费马小定理
  $$若p是质数，则对于任意整数a,有a^p\equiv{a(mod p)}$$

• 欧拉定理
  $$若正整数a,n互质，则a^{\phi{(n)}}\equiv1(mod n),其中\phi{n}为欧拉函数$$

• 欧拉定理的推论
  $$若正整数a,n互质，则对于任意正整数b，有a^b\equiv a^{bmod\phi{(n)}}(mod n)$$

取模下的计算技巧 【加、减、乘、乘方、除】

对于要求我们把答案对一个质数 p取模后输出：

• 对于a + b, a - b, a * b这样的算式，可在计算前先把a,b对p取模

• 对于乘方算式，根据欧拉定理的推论，可以先把底数对p取模、指数对 $\phi{(p)}$ 取模，再计算乘方。

  特别地，求乘方$a^b(mod n)$ ：对于当 a,n 不一定互质且 b > $\phi(n)$时，有$a^b\equiv a^{b mod \phi(n) + \phi(n)} (mod n)$

• 除法 -> 乘法逆元：$b^{p - 2}$ 即为 b 的乘法逆元。

  特别地，若只保证b,m互质，那么乘法逆元可以通过求解同余方程 $b * x \equiv 1 (mod m)$ 得到。

  因此a / b，可以先将a,b对p取模，再计算 $a * b^{-1} mod p$ 为最终结果。

2. 拓展欧几里得算法

• Bezout定理

对于任意整数 $a, b$ ,存在一对整数 $x, y$ ，满足 $ax + by = gcd(a, b)$

#include <bits/stdc++.h>
using namespace std;

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, x, y);
    int z = x; x = y; y = z - y * (a / b);
    return d;
}

int main() {
    int a, b, x, y;
    while(cin >> a >> b){
        int d = exgcd(a, b, x, y);
        cout << x << " " << y << " " << d << endl;
    }
}

x, y是以引用的方式传递的，可以求出方程 $ax + by = gcd(a, b)$的一组特解x, y，并返回a,b的最大公约数d.

• 对于一般方程$ax + by = c$，它有解当且仅当其d|c, 其中(d = gcd(a,b))。

求解：

1. 先求出ax + by = d的一组特解 $x_0, y_0$

2. $x_0,y_0$同时乘上 $c/d$，就是ax + by = c的一组特解：$(c/d)x_0,(c/d)y_0$.

3. 事实上，方程ax + by = c的通解可以表示为：
   $$x = \frac{c}{d}x_0 +k\frac{b}{d}, \ \ \ \ \ \ \ \ \ \ y = \frac{c}{d}y_0 -k\frac{a}{d} \ (k\in{Z}, d =gcd(a,b))$$

3. 线性同余方程

给定整数a,b,m 求一个整数 x 满足 $a * x \equiv b (mod m)$, 或者给出无解。

1. $a * x \equiv b (mod m)$ 改写成 $a * x + m * y= b$

2. 根据Bezout定理，方程有解当且仅当 $gcd(a,m)|b$

3. 若有解，可通过拓展欧几里得算法求出 $x_0, y_0$, 满足 $a * x_0 + m * y_0 = gcd(a, m)$

4. 然后，有 $x = x_0 * b / gcd(a, m)$ 就是原线性同余方程的一个特解

5. 方程的通解为 $x = \frac{x_0 * b}{gcd(a, m)} + k\frac{m}{gcd(a, m)}, (k \in Z)$

4. 中国剩余定理

设 $m_1,m_2,…,m_n$ 是两两互质的整数，$m \ =\ \prod_{i = 1}^nm_i\ $, $M_i\ = \ m/m_i\ $, $t_i$ 是线性同余方程 $M_it_i \equiv 1\ (mod\ m_i)$ 的一个解。对于任意的 n 个整数 $a_1,a_2,…a_n$ ，方程组
$$\begin{cases} x \equiv a_1 (mod\ m_1)\\\ x \equiv a_2 (mod\ m_2)\\\ … \\\ x \equiv a_n (mod\ m_n)\\\ \end{cases}$$

有整数解，解为 $x = \sum_{i = 1}^na_iM_it_i$。