(Debug) TIOJ 1752 妹妹的汽水
Description 雖然經歷了這場讓人魂飛魄散的事件,但是經過護士姊姊細心診斷確定他的人及屬性都沒受創之後,妁艷回到了家。 隔天去了學校,學習了更多技能之後發現身體感覺並沒有什麼異狀。可是體內感覺卻有股蠢蠢欲動的力量……。 回到了家,突然想到昨天妹妹借的書還沒還給他,就去找妹妹。可是,妁艷在門外叫了好幾聲都沒反應,他就逕自進入妹妹的房間。 「喔哈哈!」進來之後發現妹妹不在,妁艷不自覺的笑了。他開始尋找目標物,從書櫃、抽屜、書包、床鋪、衣櫃等等地方仔細搜索之後,終於在書桌上找到了那本書。 「奇怪?」書上放著一張紙條,使妁艷有點疑惑,上面寫著:「2,3,5,7,11,13,17,…。」 聰明的妁艷當然一看又知道是一串質數。找的口有點渴的妁艷,拿起桌上喝了一半的汽水準備一飲而盡,猛然發現蓋子竟然打不開,而且瓶蓋上還印了一個正整數 n 和一個質數 p,仔細一看他才發現紙上還寫了:「打開汽水需要找出第 p 個冒出的泡泡編號。」 為了喝到汽水,妁艷研究出了這種汽水冒泡的規律。 泡泡原本的順序是 n 到 1,也就是 n,n−1,n−2,…,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 個比。 泡泡最後的位置順序的倒序就是冒泡順序。 例如 n=8, 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 整除) ...