1 扩展欧几里得算法（ax+by=gcd(a,b)的求解）

1.1 问题描述

给定两个非零整数 a 和 b ，求一组整数解 (x, y)，使得ax+by=gcd(a,b)成立，其中gcd(a,b)表示a和b的最大公约数。

1.2 求出一组解

int gcd(int a,int b){
    if(b==0) return a;
    else return gcd(b, a%b);
}

1. 在gcd算法中，到达递归边界时，a变量存放的是gcd，b变量存放的是0，显然 a*1+b*0=gcd成立，即x=1、y=0。
2. 未到达递归边界时，a*x1+b*y1=gcd成立；进行下一步递归计算，b*x2+(a%b)*y2=gcd成立。可获得等式：gcd = a*x1+b*y1 = b*x2+(a%b)*y2 = b*x2+(a-(a/b)*b)*y2 = a*y2+b*(x2-(a/b)y2)，这就是(x, y)的递推关系。

// 采用了引用的方式，当函数调用结束时，x与y就是所求的解
int exGcd(int a,int b,int &x,int &y){
    if(b==0){  // 到达递归边界
        x=1;
        y=0;
        return a;
    }

    // 未到达递归边界
    int g = gcd(b, a%b, x, y);
    int temp = x;
    x=y;  // x1 = y2
    y=temp-a/b*y;  // y1=x2-(a/b)y2
    return g;
}

1.3 求出通解

1. 设exGcd函数求出的一组解为 x0、y0
2. 设通解为 x0+sx、y0-sy
3. a*(x0+sx)+b*(y0-sy)=gcd=a*x+b*y，易得a*sx=b*sy，于是 。为了让sx和sy尽可能小（即让通解x0+sx、y0-sy尽肯能具有代表性），分子和分母的值要互质，于是取，得sx和sy的最小取值是b/gcd和a/gcd。
4. 得通解：，其中K为任意整数
5. x和y的所有解分别以和为周期 ，其中x的最小非负整数解为

2 方程 ax+by=c的求解

2.1 问题描述

给定两个非零整数 a 和 b ，求一组整数解 (x, y)，使得ax+by=c成立，其中c为任意整数。

2.2 问题的解

（具体的推导过程，参见1.2部分和1.3部分）

1. 假设ax+by=gcd有一组解(x0, y0)
2. ax+by=c存在解的充要条件是c%gcd==0，且一组解等于
3. 通解为：，其中K为任意整数

3 同余式 axc(mod m) 的求解

3.1 同余式

对于整数a、b、m来说，如果m整除a-b（即 (a-b)%m==0 ），那就说a与b模m同余，对应的同余式为 ab(mod m)，m称为同余式的模。

每一个整数都各自与[0, m)中唯一的整数同余。

3.2 将同余式axc(mod m)转化为方程 ax+by=c的形式

1. axc(mod m) ax-c = -my ax+my=c
2. 通过求解ax+my = gcd(a,m)得到 (x0, y0)
3. 得到ax+my=c的通解
4. 当K分别取0、1、2、....、gcd(a, m)-1时，所得到的解在模m意义下是不同的，而其他解都可以对应到K取gcd(a, m)个数值之一。
5. 仅当c%gcd(a, m)==0时，同余式方程才有解，且恰有gcd(a, m)个模m意义下不同的解

4 逆元的求解以及 (b/a)%m 的计算

4.1 乘法逆元

1. 两个整数的乘积模m后等于1，就称它们互为m的逆元。
2. ab1(mod m)

4.2 逆元的用处

1. 计算 (b/a)%m 【b是a的整数倍】。
2. 乘法取模：(b*a)%m = ((b%m)*(a%m))%m成立
3. 除法取模：(b/a)%m = ((b%m)/(a%m))%m不成立，(b/a)%m = ((b%m)/a)%m不成立
4. 通过找到a模m的逆元x，就有 (b/a)%m = (b*x)%m，从而把除法取模转换为乘法取模，这对于解决被除数b非常大的问题来说是非常实用的。

4.3 求a模m的逆元

1. 即求同余式ax1(mod m)
2. 在实际使用中，把x的最小整数解称为a模m的逆元
3. 若gcd(a, m)!=1，那么同余式无解，a不存在模m的逆元
4. 若gcd(a, m)==1，那么同余式在(0, m)上有唯一解。使用exGcd函数解出x0之后， 就是所需要的逆元。

// 求解a模m的逆元  并返回
int inverse(int a,int m){
    int x,y;
    int g = exGcd(a, m, x, y);   // 求解 ax+my=1
    return (x%m + m) % m;
}

4.4 gcd(a, m)!=1情况下 求解 (b/a)%m

1. (b/a)%m = (b%(am))/a
2. 需要注意a和m的乘积太大可能会出现溢出的现象