$\Huge\color{orchid}{点击此处获取更多干货}$

裴蜀定理与线性同余方程

求解$a*x\equiv b(mod~m)$等价于模$m$意义下求解$a*x+m*y=b$，之前已经介绍过$a*x+b*y=gcd(a,b)$的求解方式，那么对于这次要求解的方程，左右两边同时用$gcd(a,m)$去除可得$a/gcd(a,m)*x+m/gcd(a,m)*y=b/gcd(a,m)$。毫无疑问，$x,y$前面的系数都为整数，那么$b/gcd(a,m)$也必须是整数，方程才有${x,y}$的整数解。由此，我们得出了裴蜀定理的一个表述方式：关于${x,y}$的方程$a*x+b*y=c$有整数解的充要条件就是$c\%gcd(a,b)=0$

在保证了$b\%gcd(a,m)$的情况下，可以先求$a*x+m*y=gcd(a,m)$的解，然后用它乘上相对应的倍数$k=b/gcd(a,m)$，由于是模$m$意义下的乘法，故还需要对$m$取模。这里还是不能用$\text{size_t}$，并且由于取模前用$\text{int}$可能溢出，所以可以使用$\text{long long}$

C++ 代码

/**
 * @brief 扩展欧几里得算法的64位版
 */
long long exGcd(
    long long a, long long b, 
    long long& x, long long& y
) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long gcd = exGcd(b, a % b, x, y), ox = x, oy = y;
    x = oy;
    y = ox - (a / b) * oy;
    return gcd;
}

/**
 * @brief 解方程a*x=b(mod m)
 * @param a,b,m 对应的三个参数
 * @return x的值
 * @retval LLONG_MAX 无整数解
 */
long long solveLCE(long long a, long long b, long long m) {
    long long x, y, gcd = exGcd(a, m, x, y);
    if (b % gcd != 0) {
        return LLONG_MAX;
    }
    return (x * b / gcd) % m;
}