拓展欧几里得

概念

• 欧几里得算法 ^bd4826 $(a,b)=(b,a(\mathrm{mod}b))$ 即 a与b的最大公约数等于b和a模b的最大公约数

Link to original

• 拓展欧几里得算法 对于一对正整数a，b，必至少存在一组整数x, y使得 $ax+by=gcd(a,b)$ 证明
  1. 整数可以正负
  2. 有 $ax+by$ 必定是a,b最大公约数的倍数，则绝对值最小时，有$ax+by=gcd(a,b)$ 成立

实现

推导可得，由于最大公约数相同，将mod运算拆开

拓展欧几里得 2024-02-27 22.28.31.excalidraw

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠

Text Elements

递归结果的系数关系 这一个的大数系数与前一个的小数系数 之间的等式关系

这个的小数系数等于 前一个的大数系数

Link to original

代码

int exgcd(int a, int b, int &x, int &y)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);  //当出来后，说明找到了x y，按关系变化
	y -= a / b * x;  // 上一个的小数系数由这一个大数系数求得，由于交叉，这一                      个的小数系数不变就是上一个的大数系数
    
    return d;
}

线性同余方程

求 x 使得 $ax\equiv bmodm$

化简：$ax=m\ast y+b$ y是取余的倍数 即 $ax-my=b$ $ax+my=b$ 由拓展欧几里得算法可以求得，当b是a和m最大公约数的倍数时，方程有解(x, y)

//程序几乎一样，只是输出加了判断
 
	//如果不是倍数，则无解
	if(b % d) cout << "impossible" << endl;
	else cout << x * b / d % m << endl;   // 求得x并非最小解（因为（x,y)解得对数很多，有可能算出来是m的倍数+b，为了限制范围所以再取模

中国剩余定理

由$x\equiv a_i(modm)$ n项构成的方程组

构造 $M=m_1{m}_2{m}_3\dots \dots m_n,M_i=M/m_i$ 可以得到 $x=a_i{M}_i{M}_i^{-1}$ 的累加 是方程的解

因为对于每一项，有$M_i{M}_i^{-1}$ 取余$m_i$ 为1，$a_i$留下，而其他项$M_{i+k}$ 中存在$M_i$被消去，则结果剩下$a_i$

计算方法是

1. 通过拓展欧几里得求解$M{M}^{-1}\equiv 1(modm)$
2. 再累加计算x的取值

#include <iostream>
#include <algorithm>
 
using namespace std;
 
typedef long long LL;
 
const int N = 30;
 
LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if(!b)
    {
        x = 1; y = 0;
        return a;
    }
    
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    
    return d;
}
 
int main()
{
    int n;
    cin >> n;
 
    LL a1, m1;
    cin >> a1 >> m1;  //读第一组
    
    bool flag = true;
    
    for(int i = 0; i < n-1 ; i ++)  //循环里中每次合并两组
    {
        LL a2, m2;
        
        cin >> a2 >> m2;
        
        LL k1, k2;
        
        LL d = exgcd(a1, a2, k1, k2);
        
        if((m2-m1) % d)
        {
            flag = false;
            break;
        }
        
        k1 = k1 * (m2-m1) / d;
        LL t = a2 / d;
        k1 = (k1 % t + t) % t;  //按公式取最小正余数
        
	    //按公式变化
        m1 = k1 * a1 + m1;
        a1 = (a1 / d * a2); 
    }
    
    if(flag) cout << (m1 % a1 + a1) % a1 << endl;
    else  cout << "-1" << endl;
    
    return 0;
}

分析

关于最小公倍数

Transclude of 数学#^717aa2