裴蜀定理

定義

裴蜀定理，又稱貝祖定理（Bézout's lemma）、貝祖等式（Bézout's identity）。是一個關於最大公約數的定理。

其內容是：

設 \(a,b\) 是不全為零的整數，對任意整數 \(x,y\)，滿足 \(\gcd(a,b)\mid ax+by\)，且存在整數 \(x,y\), 使得 \(ax+by=\gcd(a,b)\).

證明

對於第一點

由於 \(\gcd(a,b)\mid a,\gcd(a,b)\mid b\)

所以 \(\gcd(a,b)\mid ax,\gcd(a,b)\mid by\)，其中 \(x,y\) 均為整數

因此 \(\gcd(a,b)\mid ax+by\)

對於第二點

若任何一個等於 \(0\), 則 \(\gcd(a,b)=a\). 這時定理顯然成立。
若 \(a,b\) 不等於 \(0\).

由於 \(\gcd(a,b)=\gcd(a,-b)\),

不妨設 \(a,b\) 都大於 \(0\)，\(a\geq b,\gcd(a,b)=d\).

對 \(ax+by=d\), 兩邊同時除以 \(d\), 可得 \(a_1x+b_1y=1\), 其中 \((a_1,b_1)=1\).

轉證 \(a_1x+b_1y=1\).

我們先回顧一下輾轉相除法是怎麼做的，由 \(\gcd(a, b) \rightarrow \gcd(b,a\mod b) \rightarrow \dots\) 我們把模出來的數據叫做 \(r\) 於是，有

\[ \gcd(a_1,b_1)=\gcd(b_1,r_1)=\gcd(r_1,r_2)=\cdots=(r_{n-1},r_n)=1 \]

把輾轉相除法中的運算展開，做成帶餘數的除法，得

\[ \begin{aligned}a_1 &= q_1b_1+r_1 &(0\leq r_1<b_1) \\ b_1 &= q_2r_1+r_2 &(0\leq r_2<r_1) \\ r_1 &= q_3r_2+r_3 &(0\leq r_3<r_2) \\ &\cdots \\ r_{n-3} &= q_{n-1}r_{n-2}+r_{n-1} \\ r_{n-2} &= q_nr_{n-1}+r_n \\ r_{n-1} &= q_{n+1}r_n\end{aligned} \]

不妨令輾轉相除法在除到互質的時候退出則 \(r_n=1\) 所以有（\(q\) 被換成了 \(x\)，為了符合最終形式）

\[ r_{n-2}=x_nr_{n-1}+1 \]

即

\[ 1=r_{n-2}-x_nr_{n-1} \]

由倒數第三個式子 \(r_{n-1}=r_{n-3}-x_{n-1}r_{n-2}\) 代入上式，得

\[ 1=(1+x_nx_{n-1})r_{n-2}-x_nr_{n-3} \]

然後用同樣的辦法用它上面的等式逐個地消去 \(r_{n-2},\cdots,r_1\),

可證得 \(1=a_1x+b_1y\). 這樣等於是一般式中 \(d=1\) 的情況。

推廣

逆定理

設 \(a, b\) 是不全為零的整數，若 \(d > 0\) 是 \(a, b\) 的公因數，且存在整數 \(x, y\), 使得 \(ax+by=d\)，則 \(d = \gcd(a, b)\)。

特殊地，設 \(a, b\) 是不全為零的整數，若存在整數 \(x, y\), 使得 \(ax+by=1\)，則 \(a, b\) 互質。

多個整數

裴蜀定理可以推廣到 \(n\) 個整數的情形：設 \(a_1, a_2, \dots, a_n\) 是不全為零的整數，則存在整數 \(x_1, x_2, \dots, x_n\), 使得 \(a_1 x_1 + a_2 x_2 + \cdots + a_n x_n=\gcd(a_1, a_2, \dots, a_n)\)。其逆定理也成立：設 \(a_1, a_2, \dots, a_n\) 是不全為零的整數，\(d > 0\) 是 \(a_1, a_2, \dots, a_n\) 的公因數，若存在整數 \(x_1, x_2, \dots, x_n\), 使得 \(a_1 x_1 + a_2 x_2 + \cdots + a_n x_n=d\)，則 \(d = \gcd(a_1, a_2, \dots, a_n)\)。

應用

Codeforces Round #290 (Div. 2) D. Fox And Jumping

給出 \(n\) 張卡片，分別有 \(l_i\) 和 \(c_i\)。在一條無限長的紙帶上，你可以選擇花 \(c_i\) 的錢來購買卡片 \(i\)，從此以後可以向左或向右跳 \(l_i\) 個單位。問你至少花多少元錢才能夠跳到紙帶上全部位置。若不行，輸出 \(-1\)。

分析該問題，發現想要跳到每一個格子上，必須使得所選數 \(l_{i_1}, \dots, l_{i_k}\) 通過數次相加或相減得出的絕對值為 \(1\)，也即存在整數 \(x_1, \dots, x_n\) 使得 \(l_{i_1} x_1 + \cdots + l_{i_k} x_k = 1\)。由多個整數的裴蜀定理逆定理，這相當於從數組 \(l_1, \dots, l_n\) 選擇若干個數，滿足它們的最大公因數為 1，同時要求代價和最小。

解法 1：我們可以轉移思想，因為這些數互質，即為 \(0\) 號節點開始，每走一步求 \(\gcd\)（節點號，下一個節點），同時記錄代價（求邊權），就成為了從 \(0\) 通過不斷 \(\gcd\) 最後變為 \(1\) 的最小代價。

由於：互質即為最大公因數為 \(1\)，\(\gcd(0,x)=x\) 這兩個定理，可以證明該算法的正確。選擇優先隊列優化 Dijkstra 求解。

不過還有個問題，即為需要記錄是否已經買過一個卡片，開數組標記由於數據範圍達到 \(10^9\) 會超出內存限制，可以想到使用 unordered_map（比普通的 map 更快地訪問各個元素，迭代效率較低，詳見 STL-map）

解法 2：從數組 \(l_1, \dots, l_n\) 選擇若干個數，滿足它們的最大公因數為 1，且代價和最小，由此可以想到 0-1 揹包問題。

設 \(f_{i, j}\) 表示考慮前 \(i\) 個數且最大公因數為 \(j\) 的最小代價，則有轉移方程：

\[ f_{i, j} = \min_{\gcd(k, l_i) = j} f_{i - 1, k} + c_i. \]

DP 後最終的總代價即為 \(f_{n, 1}\)。

如同一般的 0-1 揹包問題，可以用滾動數組優化，去掉第一維。而這裏 300 個數可達的最大公因數 \(j\) 是很稀疏的，因此還可以使用 unordered_map 代替數組儲存下標 \(j\)，優化內存並進一步減少枚舉量。

實際上，這裏解法 1 建出的圖便是解法 2 中動態規劃的狀態轉移圖，解法 2 相當於用動態規劃求有向無環圖的最短路，因此解法 1 和解法 2 是等價的。但解法 2 無需儲存全圖，同時 DP 的時間複雜度為 \(O(n + m)\)，相比 Dijkstra 算法更低，因此解法 2 在時間和空間上更優。

進一步結論

對自然數 \(a\)、\(b\) 和整數 \(n\)，\(a\) 與 \(b\) 互素，考察不定方程：

\[ ax+by=n \]

其中 x 和 y 為自然數。如果方程有解，稱 n 可以被 a、b 表示。

記 \(C=ab-a-b\)。由 a 與 b 互素，C 必然為奇數。則有結論：

對任意的整數 n，n 與 \(C-n\) 中有且僅有一個可以被表示。

即：可表示的數與不可表示的數在區間 \([0,C]\) 對稱（關於 C 的一半對稱）。0 可被表示，C 不可被表示；負數不可被表示，大於 C 的數可被表示。

證明

由於 a、b 互素，因此原方程有整數解。設解為：

\[ \begin{cases}x=x_0+bt\\y=y_0-at\end{cases} \]

其中 t 為整數。取適當的 t，使得 y 位於 0 到 \(a-1\) 之間。這隻需在 \(y_0\) 上加上或減去若干個 a，即可得到這樣的 t。

第一步：證明大於 C 的數都可以被表示。當 n 大於 C 時：

\[ ax=n-by>ab-a-b-by\geqslant ab-a-b-b(a-1)=-a \]

於是 x 也是非負整數。

第二步：證明 C 不可被表示，進而 n 與 \(C-n\) 不可能都被表示。

反證法。若 \(ax+by=ab-a-b\) 有非負整數解 x、y，則：

\[ ab=a(x+1)+b(y+1) \]

由於 a 與 b 互素，所以 a 整除 \(y+1\)，b 整除 \(x+1\)，a 不超過 \(y+1\)，b 不超過 \(x+1\)。於是有：

\[ ab=a(x+1)+b(y+1)\geqslant ab+ab=2ab \]

矛盾！第二步證完。

第三步：證明如果 n 不可被表示，則 \(C-n\) 可被表示。

由上可知，若 n 不可被表示，由於上述方程中已規定 y 在 0 到 \(a-1\) 之間，則 x 為負。所以：

\[ ab-a-b-ax-by=a(-x-1)+b(a-1-y) \]

顯然 \(-x-1\) 和 \(a-1-y\) 均非負，於是 \(C-n\) 可被表示。

幾何意義

重新觀察方程 \(ax+by=n\)，將它看成一條直線。直線與兩座標軸在第一象限圍成三角形。

當 \(n<ab\) 的時候，這個直線在第一象限，至多隻能通過一個整點。

根據上述討論：當 n 可以被表示的時候，直線恰好經過一個整點；當 n 不可以被表示的時候，直線不經過整點（在第一象限）。

這結論也可以理解為：作三角形 \((0,0)(b,0)(0,a)\)。隨着 n 從 0 不斷增加，直線向右上方平移，整點會一個一個地通過直線，直到最後才撞上兩個整點。

因此，小於等於 n 的能被表示的非負整數的數量，恰好就是直線 \(ax+by=n\)（含）與兩座標軸（含）在第一象限圍成三角形覆蓋的整點個數。

另一種解釋

考慮模 b 意義下每個剩餘系中最小能被表示的值是多少——大於他們的可以通過增加若干個 b 得到。

觀察原方程，a 的若干倍數 \(0, a,\cdots, (b−1)a\) 在 \(\pmod b\) 意義下互不相同。這些數恰好是這些最小值。那麼當 \(n<ab\) 時，小於等於 n 的能被表示的非負整數的數量是：

\[ \sum\limits_{i=0}^{\left[\frac{n}{a}\right]}\left[\frac{n − ia}{b}\right] \]

這是一個非常經典的直線下整點問題，恰好是這條直線：

\[ y=-\frac{a}{b}x+\frac{n}{b} \]

即 \(ax+by=n\)。

使用類歐幾里得算法可以在 \(O(\log \max(a,b))\) 的時間內求解。因此我們得到了計算小於等於 n 的能被表示的非負整數的數量的工具。

題目

P3951 NOIP2017 提高組小凱的疑惑/藍橋杯 2013 省買不到的數目

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用