雖然經歷了這場讓人魂飛魄散的事件,但是經過護士姊姊細心診斷確定他的人及屬性都沒受創之後,妁艷回到了家。
隔天去了學校,學習了更多技能之後發現身體感覺並沒有什麼異狀。可是體內感覺卻有股蠢蠢欲動的力量……。
回到了家,突然想到昨天妹妹借的書還沒還給他,就去找妹妹。可是,妁艷在門外叫了好幾聲都沒反應,他就逕自進入妹妹的房間。
「喔哈哈!」進來之後發現妹妹不在,妁艷不自覺的笑了。他開始尋找目標物,從書櫃、抽屜、書包、床鋪、衣櫃等等地方仔細搜索之後,終於在書桌上找到了那本書。
「奇怪?」書上放著一張紙條,使妁艷有點疑惑,上面寫著:「2,3,5,7,11,13,17……。」
聰明的妁艷當然一看又知道是一串質數。找的口有點渴的妁艷,拿起桌上喝了一半的汽水準備一飲而盡,猛然發現蓋子竟然打不開,而且瓶蓋上還印了一個正整數n和一個質數p,仔細一看他才發現紙上還寫了:「打開汽水需要找出第p個冒出的泡泡編號。」
為了喝到汽水,妁艷研究出了這種汽水冒泡的規律。
1.泡泡原本的順序是n到1,也就是n,n-1,n-2,……,3,2,1。
2.從時間t=0開始每秒會有些泡泡跟其他泡泡位置交換。
3.奇妙的是,它們都遵守第t秒內時只有被編號第t個質數q整除的泡泡才可能變位置。
4.第t秒內,對第i個被q整除的泡泡編號a會跟第i+1個被q整除的泡泡編號b比大小,
如果a大於b,泡泡a和b就會交換位置,a繼續跟第i+2個比,否則用b跟第i+2個比。
5.泡泡最後的位置順序的倒序就是冒泡順序。
例如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整除)
之後順序就不會改變
所以冒泡順序是1,8,6,2,5,4,7,3
運用他演算法的知識他打算寫個程式算出p的編號,以免等等妹妹回來了,他能喝掉妹妹的汽水嗎?
每筆輸入檔案有一筆測資。
第一行有一個非負整數T代表有幾瓶汽水。(T<3000)
接下來有T行,每行有一個正整數n和一個質數p,代表氣泡數量以及所求的第p個冒出的泡泡。
(1<=n<=1000000)
(1<=p<=n)
對每組詢問輸出第p個冒出的泡泡編號並換行。
原TIOJ1752 / Problem Setter:fenzhang
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 100 |