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

线性丢番图方程求解器代码模板("解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