数论 · 求解线性同余方程

· · 个人记录

问题

求解方程 ax+by=c。

以下摘自一本通

1 求特解

定理

对于该方程，它等价于 ax \equiv c \pmod b。

即有整数解的充要条件就是：\gcd (a,b) \equiv 0 \pmod c。

求解

根据定理，我们可以先用 扩展欧几里得算法 求出一组解 x_0,y_0，即 a*x_0+b*y_0=\gcd (a,b)。

然后两边同除 \gcd(a,b)，再同乘 c 即可得到特解。

(a*x_0+b*y_0) * c\ \div\gcd (a,b)=c

2 求通解

定理

若 a \perp b，且 x_0,y_0 为方程 ax+by=c 的一组解，

则该方程的任意解可以表示为：x = x_0 +b *t,\ y = y_0 - a*t，且对 t 为任一整数都成立。

求解

按照上述定理可以求出方程的所有解。

但实际往往让我们求最小整数解，也就是：

t = b \div \gcd(a,b),\ x = (x \bmod t+ t) \bmod t

【补】 求最小解

可以看 P1516 青蛙的约会 这道题，里面就有求最小解的部分。

详细证明看 小花的题解 有对通解、最小解公式的证明。

3 代码

用扩欧求解线性方程 ax+by=c。

inline bool linearEquation (int a, int b, int c, int &x, int &y)
{
    int gcd = exgcd (a, b);
    if (c % gcd) return false;
    int k = c / gcd;
    x *= k, y *= k;
    return true;
}

——End——