(Debug) TIOJ 1752 妹妹的汽水
Description
雖然經歷了這場讓人魂飛魄散的事件，但是經過護士姊姊細心診斷確定他的人及屬性都沒受創之後，妁艷回到了家。隔天去了學校，學習了更多技能之後發現身體感覺並沒有什麼異狀。可是體內感覺卻有股蠢蠢欲動的力量……。
回到了家，突然想到昨天妹妹借的書還沒還給他，就去找妹妹。可是，妁艷在門外叫了好幾聲都沒反應，他就逕自進入妹妹的房間。
「喔哈哈！」進來之後發現妹妹不在，妁艷不自覺的笑了。他開始尋找目標物，從書櫃、抽屜、書包、床鋪、衣櫃等等地方仔細搜索之後，終於在書桌上找到了那本書。
「奇怪？」書上放著一張紙條，使妁艷有點疑惑，上面寫著：「$2, 3, 5, 7, 11, 13, 17, \ldots$。」
聰明的妁艷當然一看又知道是一串質數。找的口有點渴的妁艷，拿起桌上喝了一半的汽水準備一飲而盡，猛然發現蓋子竟然打不開，而且瓶蓋上還印了一個正整數 $n$ 和一個質數 $p$，仔細一看他才發現紙上還寫了：「打開汽水需要找出第 $p$ 個冒出的泡泡編號。」
為了喝到汽水，妁艷研究出了這種汽水冒泡的規律。
- 泡泡原本的順序是 $n$ 到 $1$，也就是 $n, n-1, n-2, \ldots, 3, 2, 1$。
- 從時間 $t=0$ 開始每秒會有些泡泡跟其他泡泡位置交換。
- 奇妙的是，它們都遵守第 $t$ 秒內時只有被編號第 $t$ 個質數 $q$ 整除的泡泡才可能變位置。
- 第 $t$ 秒內，對第 $i$ 個被 $q$ 整除的泡泡編號 $a$ 會跟第 $i+1$ 個被 $q$ 整除的泡泡編號 $b$ 比大小，如果 $a$ 大於 $b$，泡泡 $a$ 和 $b$ 就會交換位置，$a$ 繼續跟第 $i+2$ 個比，否則用 $b$ 跟第 $i+2$ 個比。
- 泡泡最後的位置順序的倒序就是冒泡順序。
- $t=0$ 時，順序是 $8, 7, 6, 5, 4, 3, 2, 1$。
- $t=1$ 時，順序是 $6, 7, 4, 5, 2, 3, 8, 1$。($8$ 跟 $6$ 換、$8$ 跟 $4$ 換、$8$ 跟 $2$ 換且 $2, 4, 6, 8$ 都被 $2$ 整除)
- $t=2$ 時，順序是 $3, 7, 4, 5, 2, 6, 8, 1$。($6$ 跟 $3$ 換且 $3, 6$ 都被 $3$ 整除)
運用他演算法的知識，他打算寫個程式算出 $p$ 的編號，以免等等妹妹回來了，他能喝掉妹妹的汽水嗎？
Input Format
每筆輸入檔案有一筆測資。
第一行有一個非負整數 $T$ 代表有幾瓶汽水。接下來有 $T$ 行，每行有一個正整數 $n$ 和一個質數 $p$，代表氣泡數量以及所求的第 $p$ 個冒出的泡泡。
- $1 \leq T \leq 3000$
- $1 \leq n \leq 10^6$
- $1 \leq p \leq n$
Output Format
對每組詢問，輸出第 $p$ 個冒出的泡泡編號並換行。
Sample Input
8
8 2
8 3
8 5
8 7
100000 2
100000 3
100000 5
100000 7
Sample Output
8
6
5
7
100000
99999
99995
99988
Analysis
期末考結束，該來多發幾篇廢文惹 (?
這個問題我五年前 (時間過得真快 XD) 在 TIOJ 舊站寫過並 AC了；兩個月前我重新看了這個題目，居然想不到該怎麼做，在看了當時我的 AC code 後，越想越不對勁。設質數由小到大是 $p_1, p_2, p_3, \ldots$，而題目的 $p = p_k$，則顯然在 $t = 0, 1, \ldots, k-1$ 時，都不會動到 (由右到左) 第 $p_k$ 個泡泡的編號，所以可以想到一個演算法：依序在 $1, 2, \ldots, n$ 中，砍掉「能被 $p_i$ 整除的最大的數」，則第 $k$ 次砍掉的數就是答案。這麼做似乎很合理，因為「如果第 $i$ 次被砍掉的數 $a_i = n - (n\operatorname{mod}p_i) =: b_i$，代表 $a_i$ 在 $t<i$ 都不會被換掉；如果第 $i$ 次被砍掉的數 $a_i$ 不是 $b_i$，可以知道在之前的幾次交換 (say, $t = j_1, j_2, \ldots$) 時，$b_i, b_i-p, \ldots, a_i+p$ 被移到 $p_{j_1}, p_{j_2}, \ldots$ 的位置，因此第 $i$ 次交換後，由於 $a_i$ 沒辦法跟右邊的其他泡泡交換，$p_i$ 位置就是 $a_i$」。
既然我用了「似乎很合理」這幾個字，代表上面那一串根本在唬爛。首先，我必須確認有沒有其他能被 $p_i$ 整除且比 $a_i$ 小的數被丟到 $p_i$ 位置後面，才能確定交換後 $p_i$ 位置是 $a_i$；另一方面，就算第 $i$ 次交換後 $p_i$ 位置真的是 $a_i$，我還必須確認接下來 $a_i$ 不會被交換掉。
其實原本我是打算證明上面那個演算法的正確性的，但還好 (?) 沒證出來。越想越覺得不對勁後，便造出了反例。一個 $n$ 最小的反例是 $n = 77, p = 5$，不難驗證這真的是反例：那個演算法會得到 $70$，可是答案是 $77$。題外話，我最早造出來的反例是 $n=11450, p=107$，超肥 orz。
在向管理員反應了這件事後，現在那題已經 rejudge 了，所以過去的 AC code 全部重收了 WA www。
留言
張貼留言