python/TangDou/AcWing/NumberTheory/扩展欧几里得解不定方程的步骤.cpp

#include <bits/stdc++.h>

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() {
    /* 原始方程 4x+6y=10 求x,y的一组解

    分析及求解步骤：
    此题中a=4,b=6,c=10
    1. 求d=gcd(a,b)=gcd(4,6)=2
    2. 判断 2|c即 10%2=0，方程有解，如果不能整除，此处可以直接返回方程无整数解
    3. 化简方程为 a/d*x+b/d*x=c/d 得到 4/2*x+6/2*y=10/2
       => 2x+3y=5 此方程与原始方程解是一样的，我们最终对这个方程下手。
    4. 如可解此方程呢？我们有一个好用的定理：扩展欧几里得可以解类似的方程
       ax+by=gcd(a,b)!
       但问题是按扩欧的描述，我们现在能计算的是 2x+3y=1的方程解！！！
       不是原方程2x+3y=5的解!!
       该怎么办呢？
       设 x0,y0为2x+3y=1的解，那么原方程的一组解就是：
       x1=5*x0,y1=5*y0!!!!

       为什么呢？原因很简单： 2x+3y=1 左右都乘以5
       2*(x*5)+3*(y*5)=5
       对比一下原方程 x1=x0*5,y1=y0*5啊~
    */
    LL x, y;
    exgcd(2, 3, x, y);
    printf("2x+3y=1 -> x=%lld y=%lld\n", x, y);
    printf("2x+3y=5 -> x=%lld y=%lld", 5 * x, 5 * y);
    return 0;
}