alan23273850 的刷題筆記
  1. 首頁
  2. /
  3. 3. ZEROJUDGE 題庫
  4. /
  5. d287: 古怪的數學家

d287: 古怪的數學家

Tags: math, number-theory, self-thinking-proof

出處：https://zerojudge.tw/ShowProblem?problemid=d287
提交：https://zerojudge.tw/Submissions?problemid=d287&account=allllllan123456

問題：假設現在有一個梯子，規定每次在上面都只能上升 $a\in[1,2^{31}-1]$ 階、下降 $b\in[1,2^{31}-1]$ 階。如果吾人能夠從地面 (第 0 階) 開始，透過規定的移動方式上上下下爬到梯子的最頂端 (第 $n$ 階)，然後再度透過規定的移動方式上上下下回到地面。求 $n$ 的最小值。

解法：公式解為 $n = a + b - \gcd(a,b)$。但這題的證明實在精妙，網路上都找不到類似的，板主費了好大一番功夫才想出來。

證明：

  1. 先考慮 $\gcd(a, b) = 1$ 的情況，我們想先證明在這個條件底下 $n = a + b - 1$ 會是一個可行的階數。

    i. 不會動彈不得：若一個 $n'$ 階的梯子上存在某個高度 $k\in[0, n']$ 既無法繼續上升也無法繼續下降，那 $k$ 勢必要同時滿足 $k\le b-1$ 以及 $n'-a+1\le k$，兩個不等式相加會得到 $n'\le a+b-2$；因為我們的 $n\not\le a+b-2$，所以階數 $n$ 的梯子上不存在任何一個高度會動彈不得，每個高度都可以繼續上升或下降。

    ii. 移動方向唯一：若一個 $n'$ 階的梯子上存在某個高度 $k\in[0, n']$ 可以讓爬梯者自由選擇是要上升還是下降，那麼 $k$ 勢必要同時滿足 $b\le k$ 以及 $k\le n'-a$，兩個不等式相加會得到 $n'\ge a+b$；因為我們的 $n\not\ge a+b$，所以階數 $n$ 的梯子上的每個高度至多都只能選擇繼續上升或下降其中一者。再搭配上一點提到的可移動性，於是從每個高度出發之後的下個歸著點一定存在且唯一。

    iii. 下降就是上升：因為 $-b\equiv a\pmod{a+b}$，在階數 $n$ 的梯子上便可以視下降 $b$ 為上升 $a$ 再$\pmod{n+1}$，等於說第 $k$ 步的高度剛好就是 $a\cdot k\pmod{n+1}$。

    衝著這個規律，因為 $a$ 和 $n+1$ 互質的關係，我勢必能找到一個整數 $k_1\in[1,n]$ 使得 $a\cdot k_1\equiv n\pmod{n+1}$，也能找到另一個最小正整數 $k_2=n+1$ 使得 $a\cdot k_2\equiv 0\pmod{n+1}$，這就說明了階數 $n$ 可以讓爬梯者從地面移到頂端再回到地面。

  2. 接下來要證同樣在 $\gcd(a, b) = 1$ 的情況，所有滿足 $n' < a + b - 1$ 的階數都不可行。

    考慮方程式 $ax-by=0$，其中 $x$ 和 $y$ 分別代表上升與下降的總次數，因為 $a$ 和 $b$ 互質，其最小正整數解為 $(x,y)=(b,a)$，意味著從某個高度出發之後至少需要移動 $a+b$ 次才有可能再回到同一高度，然而當 $n' < a + b - 1$ 的時候，所有可能的高度從 $0$ 到 $n'$ 也才 $n'+1 < a + b$ 種，根據鴿籠原理，在此梯子上要回到同一高度不可能移動超過 $n'+1$ 次，也就不可能滿 $a+b$ 次，兩者造成矛盾，於是在這種梯子上我不可能從地面移到頂端再回到地面。

  3. 至於 $\gcd(a, b) > 1$ 的情況，我們可以把每 $\gcd(a, b)$ 個小階合成一大階，那原本的問題就轉變為上升 $a'=\dfrac a{\gcd(a, b)}$ 大階、下降 $b'=\dfrac b{\gcd(a, b)}$ 大階的互質版本，最後的答案 $a' + b' - 1$ 再乘上 $\gcd(a, b)$ 就是解法中的公式了。

致謝：感謝 TN Lin 同學對於這篇報告的文字排版以及數學論證給予詳細的 review！

1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5    long long a, b;
6    while (cin >> a >> b)
7        cout << a + b - __gcd(a, b) << '\n';
8    return 0;
9}

no image