数学：逆元，同余

1. 同余类（剩余类）：模m同余的所有整数构成一个集合，叫做模m的一个同余类。例如，模2时，所有的偶数都属于同余类$[0{]}_2$，所有的奇数都属于同余类$[1{]}_2$。一般的，模m有m个不同的剩余类，也就是同余类，分别是：$[0{]}_m，[1{]}_m，[2{]}_m....[m-1{]}_m$
2. 完全剩余系：从每个模 m 的同余类中各取一个数组成的集合，称为模 m 的完全剩余系。例如，模 4 的一个完全剩余系可为 { 0 , 1 , 2 , 3 } \{0, 1, 2, 3\} {0,1,2,3}，或 { 5 , − 2 , 7 , 10 } \{5, -2, 7, 10\} {5,−2,7,10}（每个数模 4 余 0,1,2,3）。
3. 简化剩余系（缩系）：若同余类中的数与 m 互质，则称该类为简化同余类。从所有简化同余类中各取一个数组成的集合，称为模 m 的简化剩余系，其元素个数为欧拉函数 $\phi (m)$。例如，模 6 时，与 6 互质的数为 1,5，故简化剩余系为 { 1 , 5 } \{1, 5\} {1,5}，$\phi (6)=2$。(不知道什么是欧拉函数的看我这篇博客—还没写）

1.2 解同余线性方程

问题描述：有：$ax\equiv b(\mathrm{mod}m)$，且$a，b，m$都是整数，$m>0$，求解 $x$。
问题等价于求解$ax+my=b$。其中 (x, y) 是整数解。这是因为 $ax\equiv b(\mathrm{mod}m)$ 意味着 ax 与 b 的差是 m 的倍数，即存在整数 y 使得 $ax-b=my$，整理后得到$ax+my=b$。

下面为解决这个问题步骤：

1.解的存在性
2.使用扩展欧几里算出贝祖系数然后求特解（所以先会介绍这个算法是什么）
3.由特解算通解

1. 解的存在性(必要性）：设$d=gcd(a,m)$，方程有解当且仅当 d 整除 b¹，记作$(d\mid b)$。

证明：首先 $ax\equiv b(\mathrm{mod}m)$的等价形式为 $ax-b=km$。
$ax-b=km$，则 $ax-km=b$，d 是 a 和 m 的公约数，即存在整数 $a^{\prime }=a/d，m^{\prime }=m/d$，使得 $a=d{a}^{\prime }，m=d{m}^{\prime }$，且$\gcd (a^{\prime },m^{\prime })=1$。
将$a=d{a}^{\prime }，m=d{m}^{\prime }$ 代入上式：$d{a}^{\prime }x-d{m}^{\prime }k=b\Rightarrow d(a^{\prime }x-m^{\prime }k)=b$
由于$a^{\prime }x-m^{\prime }k$ 是整数，记为 t，则 $b=dt$，即 $d\mid b$。

2. 扩展欧几里得算法

    扩展欧几里得算法是欧几里得算法（辗转相除法）的扩展，其核心目标是：对于给定的整数 a 和 b，不仅计算它们的最大公约数$d=\gcd (a,b)$，还找到整数 x 和 y，使得：$ax+by=d$其中，整数对 $(x,y)$ 称为贝祖系数。
    扩展欧几里得算法不仅能计算 $gcd(a,m)$，还能找到整数$x_0$和 $y_0$，使得：$a\cdot x_0+m\cdot y_0=\gcd (a,m)$若 b 是 $\gcd (a,m)$ 的倍数（即 $b=d\cdot k$，其中 $d=\gcd (a,m)$，则原方程的一个特解为：$x=x_0\cdot k\text{和}y=y_0\cdot k$

什么是贝祖系数？先看贝祖定理：

贝祖定理：对于任意整数 a 和 b，存在整数 x 和 y，使得 $ax+by=\gcd (a,b)$。特别地，当 a 和 b 互质时，存在 x 和 y 使得 $ax+by=1$。

欧几里得算法基于递归式$\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$，而扩展算法在计算 GCD 的同时，通过回溯保存每一步的线性组合系数。

先说明一下欧几里得算法的基本流程：
下面是欧几里得算法（辗转相除法）

#include<iostream>
using namespace std;

int gcd(int a,int b)   //递归     示例 a=24   b=9 
{
	if(b==0)
		return a;
	return gcd(b,a%b);
}

int gcd(int a,int b)   //迭代
{
	while(b!=0)
	{
		int temp=b;
		b=a%b;
		a=temp;
	}
	return a;
}

扩展欧几里得算法求贝祖系数：

// 扩展欧几里得算法：求 gcd(a, m) 及贝祖系数 x, y
int extendedGCD(int a, int m, int& x, int& y) //一开始x，y什么值都没有，空
{
    if (m == 0) //此时gcd(a,0)=a,贝祖系数为x=1,y=0.因为a*1+0*0=a
    {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int gcd = extendedGCD(m, a % m, x1, y1);
    //m*x1+(a%m)*y1=gcd(m,a%m)

	//通过递归返回的x1,y1计算当前层的贝祖系数x,y
    x = y1;
    y = x1 - (a / m) * y1;
    return gcd;
}

通过贝祖系数求同余方程特解：

1. 原同余方程$ax\equiv b(\mathrm{mod}m)$ 等价于线性不定方程：$ax+my=b$当且仅当$\gcd (a,m)\mid b$ 时，方程有解。此时，记 $d=\gcd (a,m)$，则存在整数$k=\frac{b}{d}$，使得 $b=d\cdot k$。

2. 将贝祖等式两边同时乘以$k=\frac{b}{d}$：$a{x}_0\cdot k+m{y}_0\cdot k=d\cdot k$，由于$d\cdot k=b$，代入上式得：$a\cdot (x_0\cdot k)+m\cdot (y_0\cdot k)=b$，对比原方程 $ax+my=b$，可以发现：$x^{\prime }=x_0\cdot k=x_0\cdot \frac{b}{d}$，$y^{\prime }=y_0\cdot k=y_0\cdot \frac{b}{d}$是原方程的一组整数解，即特解。

通解：
对于同余方程 $a\cdot x\equiv b(\mathrm{mod}m)$，转化为线性方程$a\cdot x+m\cdot y=b$ 后。
特解：通过扩展欧几里得算法求得一组特解$(x_1,y_1)$，满足 $a\cdot x_1+m\cdot y_1=b$。
通解：所有解可表示为：$x=x_1+k\cdot \frac{m}{d},y=y_1-k\cdot \frac{a}{d}(k\in \mathbb{Z})$。其中$d=\gcd (a,m)$。

通解的推导过程：
设$(x_1,y_1)$ 和$(x_2,y_2)$ 是方程的两组解，则：$a\cdot x_1+m\cdot y_1=b\text{和}a\cdot x_2+m\cdot y_2=b$ 两式相减得：
$a(x_2-x_1)+m(y_2-y_1)=0\Rightarrow a(x_2-x_1)=-m(y_2-y_1)$
两边除以 $d=\gcd (a,m)$，得：$\frac{a}{d}(x_2-x_1)=-\frac{m}{d}(y_2-y_1)$
由于$\frac{a}{d}$ 和$\frac{m}{d}$ 互质，故 $(x_2-x_1)$ 必为 $\frac{m}{d}$ 的倍数，即：$x_2-x_1=k\cdot \frac{m}{d}\Rightarrow x_2=x_1+k\cdot \frac{m}{d}$
代入原方程得：$y_2=y_1-k\cdot \frac{a}{d}$

求同余方程特通解：(全部过程代码）

#include <iostream>
#include <vector>
using namespace std;

// 扩展欧几里得算法
int extendedGCD(int a, int m, int& x, int& y) {
    if (m == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int gcd = extendedGCD(m, a % m, x1, y1);
    x = y1;
    y = x1 - (a / m) * y1;
    return gcd;
}

// 求解 ax ≡ b (mod m)
vector<int> solveCongruence(int a, int b, int m) {
    vector<int> solutions;
    int x, y;
    int gcd = extendedGCD(a, m, x, y);
    
    // 检查解的存在性
    if (b % gcd != 0) {
        return solutions; // 无解
    }
    
    // 计算特解并调整到最小非负
    int x0 = x * (b / gcd);
    x0 = (x0 % m + m) % m;
    
    // 生成所有解
    int step = m / gcd;
    for (int k = 0; k < gcd; k++) {
        solutions.push_back((x0 + k * step) % m);
    }
    
    return solutions;
}

int main() {
    int a = 30, b = 6, m = 24;
    vector<int> solutions = solveCongruence(a, b, m);
    
    if (solutions.empty()) {
        cout << "无解" << endl;
    } else {
        cout << "解为: ";
        for (int x : solutions) {
            cout << x << " ";
        }
        cout << endl;
    }
    
    return 0;
}

代码难点就是，回溯的时候，子问题的x，y和原问题的x，y是如何置换的？

扩展欧几里得算法的目标是求解贝祖方程$a\cdot x+b\cdot y=\gcd (a,b)$,根据欧几里得算法的递归性质，我们知道：$\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$
因此，假设子问题: 求解$b\cdot x^{\prime }+(a\mathrm{mod}b)\cdot y^{\prime }=\gcd (b,a\mathrm{mod}b)$的解为 (x’, y’)，则原问题的解 ((x, y)) 与子问题的解存在以下关系：

1. $a\mathrm{mod}b$：$a\mathrm{mod}b=a-\lfloor \frac{a}{b}\rfloor \cdot b$其中$\lfloor \frac{a}{b}\rfloor$ 表示 a 除以 b 的商。

2. 代入子问题的贝祖方程：$b\cdot x^{\prime }+(a\mathrm{mod}b)\cdot y^{\prime }=\gcd (b,a\mathrm{mod}b)$
   替换 $a\mathrm{mod}b$：
   $b\cdot x^{\prime }+(a-\lfloor \frac{a}{b}\rfloor \cdot b)\cdot y^{\prime }=\gcd (a,b)$

3. 整理方程：$a\cdot y^{\prime }+b\cdot (x^{\prime }-\lfloor \frac{a}{b}\rfloor \cdot y^{\prime })=\gcd (a,b)$

4. 对比原问题的贝祖方程：$a\cdot x+b\cdot y=\gcd (a,b)$
   可得：
   $x=y^{\prime },y=x^{\prime }-\lfloor \frac{a}{b}\rfloor \cdot y^{\prime }$

2.逆元

在模运算中，逆元分为加法逆元和乘法逆元。
这里只介绍乘法逆元.

对于整数a和模数m，若存在整数x满足：$a\ast x\equiv 1(modm)$
则称x是a在模m下的乘法逆元，记作$a^{-1}modm$

逆元存在当且仅当a和m互质(gcd(a,m)=1)

为什么需要逆元？
因为在模运算中，$\frac{a}{b}modm$ 没有定义，所有要把除法转换成乘法，也就是$\frac{a}{b}modm=b\ast a^{-1}modm$
而求$a^{-1}$ 可以通过$a\ast a^{-1}\equiv 1(modm)$ 来求
比如：

计算 $\frac{6}{3}\mathrm{mod}7$，等价于$6\cdot 3^{-1}\mathrm{mod}7$。由于 $3\times 5=15\equiv 1\mathrm{mod}7$，故 $3^{-1}=5$，则结果为 $6\times 5=30\equiv 2\mathrm{mod}7$，与实际 $\frac{6}{3}=2$ 一致。

下面是两种方法求逆元

费马小定理求逆元(m必需为质数）

证明看我这篇文章除法求模
原理：若 m 是质数，且 a 不是 m 的倍数，则根据费马小定理：$a^{m-1}\equiv 1(\mathrm{mod}m)$两边同乘 $a^{-1}$ 得：$a^{-1}\equiv a^{m-2}(\mathrm{mod}m)$

long long quick_pow(long long a, long long b, long long mod)
 {
    long long res = 1;
    while (b) 
    {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

long long mod_inverse(long long a, long long m) {
    if (a % m == 0) return -1;  // 逆元不存在
    return quick_pow(a, m - 2, m);
}

扩展欧几里得求逆元（使用任意互质的a和m）

原理：根据贝祖定理，若 $\gcd (a,m)=1$，则存在整数 $x,y$ 使得：$a\cdot x+m\cdot y=1$两边模 m 得：$a\cdot x\equiv 1(\mathrm{mod}m)$ 因此 x 即为 a 的逆元。

因为这是贝祖定理的特殊情况，所有操作比较简单。

计算步骤：

1. 用欧几里得扩展算法求解$a\ast x+m\ast y=1$ 的一组特解
2. 逆元为$x_{0}modm$

#include <iostream>
using namespace std;

// 扩展欧几里得算法
long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

// 求逆元
long long mod_inverse(long long a, long long m) {
    long long x, y;
    long long d = exgcd(a, m, x, y);
    if (d != 1) return -1;  // 逆元不存在
    return (x % m + m) % m;  // 确保结果为正
}

int main() {
    long long a = 3, m = 7;
    long long inv = mod_inverse(a, m);
    cout << "3的逆元模7是: " << inv << endl;  // 应输出5
    return 0;
}