裴蜀定理 - NOI提高级教程

📖 裴蜀定理与线性丢番图方程

裴蜀定理 (Bézout's Identity) 描述了关于最大公约数的一个重要代数性质。它是扩展欧几里得算法的数论基础。

📐 定理核心内容

对于任意非零整数 $a$ 和 $b$，设其最大公约数 $d = \gcd(a, b)$。则关于未知数 $x$ 和 $y$ 的线性丢番图方程：

$ax + by = c$

有整数解的充分必要条件是：常数 $c$ 必须是最大公约数 $d$ 的整数倍（即 $d \mid c$）。

特别地，一定存在整数 $x_0, y_0$ 使得：

$ax_0 + by_0 = \gcd(a, b)$

📐 几何网格可视化物理证明

若将 $ax + by = c$ 视为平面直角坐标系中的一条直线，寻找它的整数解，等价于寻找这条直线所经过的整格点（坐标 $x, y$ 均为整数的点）。

当 $\gcd(a, b) \mid c$ 时，直线一定会穿过网格上的整格点，方程有无穷多组整数解。
当 $\gcd(a, b) \nmid c$ 时，直线必然会完美避开所有网格交点，在整格点缝隙中穿过，方程无整数解。

系数 a: 3

系数 b: 2

常数 c: 1

调节上方滑动条改变方程 $ax + by = c$ 的参数，查看直线与整格点交汇的动态规律。

最大公约数 gcd(a, b) 1

可解性判断 (gcd | c) 1 | 1 (有整数解)

特解 (x0, y0) (1, -1)

通解公式 x=1+2t, y=-1-3t

📐 平面整格点直线分布图

方程直线

有解交汇整格点

普通整格点

// 扩展欧几里得算法求 gcd(a,b) 及裴蜀特解 x, y
long long extGcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    long long x1, y1;
    long long d = extGcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return d;
}

// 裴蜀判定：方程 ax + by = c 是否有整数解
bool hasSolution(long long a, long long b, long long c) {
    long long x, y;
    return c % extGcd(a, b, x, y) == 0;
}

📋 几何扫描分析日志