TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

15.4% (2/13)

Submission's AC Ratio

3.8% (2/52)

Tags

Description

雖然經歷了這場讓人魂飛魄散的事件,但是經過護士姊姊細心診斷確定他的人及屬性都沒受創之後,妁艷回到了家。

隔天去了學校,學習了更多技能之後發現身體感覺並沒有什麼異狀。可是體內感覺卻有股蠢蠢欲動的力量……。

回到了家,突然想到昨天妹妹借的書還沒還給他,就去找妹妹。可是,妁艷在門外叫了好幾聲都沒反應,他就逕自進入妹妹的房間。

「喔哈哈!」進來之後發現妹妹不在,妁艷不自覺的笑了。他開始尋找目標物,從書櫃、抽屜、書包、床鋪、衣櫃等等地方仔細搜索之後,終於在書桌上找到了那本書。
「奇怪?」書上放著一張紙條,使妁艷有點疑惑,上面寫著:「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的編號,以免等等妹妹回來了,他能喝掉妹妹的汽水嗎?

Input Format

每筆輸入檔案有一筆測資。

第一行有一個非負整數T代表有幾瓶汽水。(T<3000)

接下來有T行,每行有一個正整數n和一個質數p,代表氣泡數量以及所求的第p個冒出的泡泡。
(1<=n<=1000000)
(1<=p<=n)

Output Format

對每組詢問輸出第p個冒出的泡泡編號並換行。

Sample Input 1

8
8 2
8 3
8 5
8 7
100000 2
100000 3
100000 5
100000 7

Sample Output 1

8
6
5
7
100000
99999
99995
99988

Hints

Problem Source

原TIOJ1752 / Problem Setter:fenzhang

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 6500 262144 262144 1