参考自https://www.cnblogs.com/bljfy/p/9316784.html

https://blog.csdn.net/weixin_44073496/article/details/85225355

辗转相除法

证明

设q = a / b；

r = a % b；

1）若r == 0，则b为a的最大公因数

2）设a和b有公因数d，则d为r的因数

3）设b和r有公因数d，则d为a的因数

先证明2）：设a = xd， b = yd，则r = a - bq = d（x - yq）

所以，a和b的公因数都为r的因数，也为b和r的公因数

在证明3）：b = xd，r = yd，a = bq + r = d（xq+y）

所以，b和r的公因数都为a的因数，也为a和b的公因数

所以二者公因数集相等，那么gcd也相等

所以gcd(a, b) == gcd(a, a%b)

结合1，当a%b为0时，gcd(a, 0) ==…==gcd(a, b)

代码

1
2
3
4
5
int gcd(int a, int b)
{
    if(b == 0) return a;
    return gcd(b, a % b);
}

扩展欧几里得算法

证明

贝祖定理及其证明

贝祖定理：

ax + by = c, x ∈ Z*成立的充要条件是gcd(a, b) | c

证明：

设s = gcd(a, b)，显然s | a，并且s | b

又因为x, y ∈ Z*

所以s | ax, s | by

s | ax + by

ax + by = s * t（t为整数）

所以，c是s的倍数，即，c是a，b最大公因数的倍数

扩展欧几里得算法证明

利用数学归纳法

  1. 当b == 0时：在扩展欧几里得算法的最后一步，即b == 0 时候，显然存在一对整数x = 1, y = 0，使得a * 1 + 0 * 0 = gcd(a,0)成立

  2. 设若b > 0, 则gcd(a,b) = gcd(b, a mod b)。假设存在一对整数x, y满足 b * x + (a mod b) * y = gcd(b, a mod b)成立

    因为 a mod b = a - [a / b] * b，所以式子可以变为
    bx + (a - [a / b] * b) y = ay + (x - [a / b] y) b. 这时候令 x ’ = y, y ’ = ( x - [a / b] y)
    就有ax’ + by’ = gcd(a, b).(这一步推出了下一步)

由1和2，归纳得出命题成立

代码

来自开头参考中的第二个链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y){
    if(!b){ x = 1, y = 0; return a;}
    ll d = exgcd(b,a % b, x, y);
    ll z = x; x = y; y = z - (a / b) * y;
    return d;
}
//定义变量d,x,y,调用d = exgcd(a,b,x,y) 注意x, y是引用传入。
//上述程序求出的是方程ax + by = gcd(a,b)的一组特解x,y.并返回了a,b的最大公约数
//对于更为一般的方程 ax + by = c,显然它有解的充分必要条件是d | c，d = gcd(a,b)
//所以我们可以先求出ax + by = d 的一组特解x0,y0,再同时乘上c / d, 就得到了ax + by = c 的一组特解 (c/d)x0, (c/d)y0;
/*
	更进一步方程ax + by = c的通解可表示为：
	x = c / d * x0 + k * (b / d)  //1)
	y = c / d * y0 - k * (a / d)  //2)
	其中k是任意整数，d = gcd(a,b),x0,y0是 ax + by = d的一组特解
	简略证明是将1) 2)代入ax + by.发现 k * ab / d相互抵消
*/

扩展欧几里得算法的应用

以下有点超出我的知识范围orz，先copy下来，以后慢慢看，慢慢改

解线性同余方程：

描述

给定整数a,b,m，求一个整数x 使得 a * x ≡ b (mod m), 无解则给出无解。
a * x ≡ b (mod m) 等价于a * x - b 是 m的倍数，不妨设为 -y 倍，于是该方程可以变为
a * x + m * y = b.
由前面可知该线性同余方程有解当且仅当 gcd(a,m) | b.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ll exgcd(ll a, ll b,ll &x,ll &y){
    if(!b){
        return x = 1, y = 0, a;
    }
    ll d = exgcd(b , a % b, x, y);
    ll t = x;
    x = y, y = t - (a / b) * y;
    return d;
}
//solve ax + by = c return x; // x > 0
ll solve(ll a,ll b,ll c){
    ll x,y;
    ll d = exgcd(a,b,x,y);
    if(c % d) return -1; //无解 c 不能整除gcd(a,b)
    x *= c / d ; // x = c / d * x0 + k * ( b / d)
    ll tmp = b / d;
    return (x % tmp + tmp) % tmp;  //求解正整数解x
}

特殊的线性同余方程a * x ≡ 1 (mod m)(等价于求解乘法逆元)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ll exgcd(ll a, ll b,ll &x,ll &y){
    if(!b){
        return x = 1, y = 0, a;
    }
    ll d = exgcd(b , a % b, x, y);
    ll t = x;
    x = y, y = t - (a / b) * y;
    return d;
}

ll get_inv(ll a,ll mod){
    ll x,y;
    exgcd(a,mod,x,y);
    return (x % mod + mod)%mod; //求解最小正逆元
}

扩展求解线性同余方程组

描述

先考虑两个方程组的情况t ≡ r1 ( mod a1)(1)，t ≡ r2( mod a2)(2)
(a1,a2不一定互质) 要求t(t > 0)
则有 t = a1 * x1 + r1, t = a2*x2 + r2；
变形为：a1 * x1 + a2 * (-x2) = ( r2 - r1)；
方程组有解等价于： (r2 - r1) | gcd(a1, a2);
我们可用扩展欧几里得算法求出 特解x10, x20; 求出最小正整数解x10；
那么要求的 t0 = a1 * x10 + r1;
显然 t0 满足1) 式和2)式
由此推论：t0 + k * lcm(a1,a2) 是(1)，(2)两个方程组的通解，lcm(a1,a2)都可消去。
在此通解基础上可以得到新的线性同余方程 t ≡ t0 (mod lcm(a1,a2)) （3）

两个以上的时候就等价于在先求出两个线性同余方程的通解t，在和第三个方程联立又求解一次t’，不断合并。

未完待续……

hexo的markdown渲染把*都当成斜体标志来处理，本地的typora都没有！！

害得我还得一个个加上引用来避免渲染……