线性丢番图方程求解器代码模板("解 ax + by = c 的板子")（C/C++/Java/Python多版本）

这模板用于求解线性丢番图方程 ax + by = cax+by=c，它首先通过扩展欧几里得算法检查整数解是否存在（当且仅当 cc 能被 aa 和 bb 的最大公约数整除），然后计算出方程中 xx 的一个特解，并通过模运算将其调整为其最小非负整数解，最后返回该解值；若无解则返回 -1。

1. C/C++版代码：

long long extgcd(long long a, long long b, long long &x, long long &y) {
    // 扩展欧几里得算法：计算ax+by=gcd(a,b)的解
    if (b == 0) {
        x = 1;
        y = 0;
        return a;  // gcd(a,0)=a
    }
    // 递归时交换x,y参数，减少一次临时变量赋值
    long long g = extgcd(b, a % b, y, x);
    y -= a / b * x;  // 调整y系数
    return g;
}

long long cal(long long a, long long b, long long c) {
    // 求解线性同余方程ax ≡ c (mod b)的最小正整数解
    long long x, y;
    long long gcd = extgcd(a, b, x, y);  // 求ax+by=gcd(a,b)的特解
    
    // 无解条件：c不能被gcd(a,b)整除
    if (c % gcd != 0) return -1;
    
    // 将特解扩展到方程ax+by=c
    x *= c / gcd;
    
    // 计算模数调整
    b /= gcd;
    if (b < 0) b = -b;  // 确保模数为正
    
    // 计算最小正整数解
    long long ans = x % b;
    if (ans <= 0) ans += b;  // 保证结果为正
    
    return ans;
}

2. Java版代码：

public class ExtendedGCD {
    // 封装扩展欧几里得算法的计算结果
    public static class Result {
        public long d; // 最大公约数 gcd(a,b)
        public long x; // 贝祖等式系数：满足 ax+by=d 的 x
        public long y; // 贝祖等式系数：满足 ax+by=d 的 y
        
        public Result(long d, long x, long y) {
            this.d = d;
            this.x = x;
            this.y = y;
        }
    }
    
    // 扩展欧几里得算法：计算ax+by=gcd(a,b)的整数解
    public static Result extgcd(long a, long b) {
        // 递归终止：gcd(a,0)=a，此时a*1+0*0=a
        if (b == 0) {
            return new Result(a, 1, 0);
        }
        // 递归计算并直接构造新结果（优化中间变量）
        Result res = extgcd(b, a % b);
        return new Result(res.d, res.y, res.x - a / b * res.y);
    }
    
    // 求解线性同余方程ax ≡ c (mod b)的最小正整数解
    public static long cal(long a, long b, long c) {
        Result res = extgcd(a, b);  // 计算ax+by=gcd(a,b)的特解
        long gcd = res.d;
        long x = res.x;
        
        // 无解条件：c不是gcd的倍数
        if (c % gcd != 0) return -1;
        
        // 将特解x扩展到方程ax+by=c
        x *= c / gcd;
        
        // 计算模数并确保为正
        b /= gcd;
        if (b < 0) b = -b;
        
        // 计算最小正整数解
        long ans = x % b;
        if (ans <= 0) ans += b;  // 确保结果为正
        
        return ans;
    }
}

3. Python版代码：

def extgcd(a, b):
    # 扩展欧几里得算法：计算gcd(a,b)及满足ax+by=gcd(a,b)的整数解(x,y)
    
    # 递归终止条件：b=0时，gcd=a，系数x=1,y=0满足a*x+0*y=a
    if b == 0:
        return a, 1, 0
    
    # 递归计算并直接返回调整后的系数（优化版）
    g, x1, y1 = extgcd(b, a % b)  # x1,y1是递归下层的解
    return g, y1, x1 - (a // b) * y1  # 调整系数并返回


def cal(a, b, c):
    # 求解线性同余方程ax ≡ c (mod b)的最小正整数解
    
    d, x, y = extgcd(a, b)  # 获取ax+by=gcd(a,b)的特解
    
    # 无解条件：c不能被gcd(a,b)整除
    if c % d != 0:
        return -1
    
    # 将特解扩展到原方程ax+by=c
    x *= c // d
    
    # 计算模数并确保为正
    b //= d
    if b < 0:
        b = -b
    
    # 计算最小正整数解
    ans = x % b
    if ans <= 0:
        ans += b  # 调整到正数范围
    
    return ans