TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

22.2% (6/27)

Tags

Description

話說海鞘成功地配置好了巡邏人手,開始巡邏第一天就抓到了一名入侵者。
警衛把入侵者帶到了海鞘的辦公室。

『你不是草甘嗎!你怎麼會在這裡?』海鞘看了很驚訝,在他眼前的竟然是草甘!(*)
這裡就要簡述一下草甘了,他是21年前的風雲人物,曾經獲得奧林匹克疊烏龜(ITO)金牌!
但是草甘卻在21年前疊完超級烏龜塔後銷聲匿跡,難道這些年他都躲在藏寶窟群嗎?

「嗚啦啦啦嗚啦啦嗚啦阿拉拉阿嚕嚕啦啦嚕嗚呱呱嗚嗚啦,哈哈哈哈哈」
草甘語焉不詳地笑著,突然拿出了一條長條形的地毯鋪在地板上。
海鞘定神一看,上面寫著0到(M-1)的數字。草甘站在(1 mod M)的位置開始移動。

海鞘是數學一哥前文已有提到,他很快發現草甘的移動路徑跟一個神秘數字N有關。
也就是假設他第i次在位置P,那麼第i+1次移動時他會在位置(P×N) mod M。

而且海鞘很快地發現,草甘的運動可以分成兩部份:"循環前"跟"循環"。
例如說當N=2,M=4時,草甘的運動路徑會是:1→2→0→0→0→0→…
也就是"1→2"是他的非循環部份、他的循環長度為1。

海鞘想知道草甘到底發生了什麼事,請你幫他算出草甘的"循環前"以及"循環"各有多長。

Input Format

※本題單一檔案有多筆測資,以EOF結尾。
每筆測資僅有一行含兩個數字N, M。保證1 ≤ N, M ≤ 1017。

保證M的質因數都 <= 107。

Output Format

對每筆測資輸出一行包含兩個數字,依序表示循環前以及循環的長度。

Sample Input

2 4
2 5

Sample Output

2 1
0 4

Hints

第一筆輸入:1→2→0→0→0→0→…
第二筆輸入:1→2→4→3→1→2→4→3→…

(*)詳情見建國中學2010年校內模擬賽Contest 4 prob 5 (TIOJ 1676)

Problem Source

原TIOJ1695 / ABCLS Contest, Problem E

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 6000 65536 65536