初等数论之求解二元不定方程

定理1:

设二元一次不定方程
$$ ax + by = c \\hspace{1cm} (1) $$

(其中a, b, c是整数, 且a, b都不是0), 假定有一组整数解，$x=x_0, y=y_0$。

则原式的一切整数的通解可以表示成
$$ \\left\\{ \\begin{aligned} x = x_0 + \\frac b {(a, b)}t, & \\\\ & (t \\in z) \\\\ y = y_0 - \\frac a {(a, b)}t, & \\\\ \\end{aligned} \\right. $$
定理2:

$\\hspace{1cm}(1)$式有整数解等价于$(a, b)|c$。

解法：

扩展欧几里得算法就是求解二元不定方程的手段之一

扩展中国剩余定理模板题

#include<iostream>

using namespace std;
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, y, x);
    y -= a / b * x;
    return d;
}

int main(){
    int n;
    cin >> n;
    LL a1, m1, a2, m2, k1, k2;
    cin >> a1 >> m1;
    while ( -- n){
        cin >> a2 >> m2;
        LL d = exgcd(a1, a2, k1, k2);
        if((m2 - m1) % d){
            cout << -1 << endl;
            return 0;
        }
        k1 = k1 * (m2 - m1) / d; // 特解
        k1 = (k1 % (a2 / d) + a2 / d) % (a2 / d);
        m1 = a1 * k1 + m1;
        a1 = a1 * a2 / d;
    }
    m1 = (m1 % a1 + a1) % a1;
    cout << m1 << endl;
    return 0;
}

参考书籍