對求分數ABAB，求其在KK進制下是有限小數還是循環小數。如果是有限小數，求小數點後的位數；如果是循環小數，則求混循環部分和循環節的長度又分别是多少。
InputInput
OuputOuput
這道數論，好難啊。。。
證明我肯定是看不懂了。隻能按照題解所說的打，但是什麼都不懂。
在這裡把 題解 的證明放一下。
首先把ABAB約分成既約分數。設 a[1]=Aa[1]=A，r[n]r[n] 為原分數小數點後第nn位的數。 顯然有 r[1]=floor(K×a[1]B)r[1]=floor(K×a[1]B)。 剩下來的餘數 a[2]=K×a[1]a[2]=K×a[1] modmod BB。 依此類推我們有 r[n]=floor(K×a[n]B)r[n]=floor(K×a[n]B)，a[n]=K×a[n−1]a[n]=K×a[n−1] modmod BB。 不難發現如果 a[p]=a[q]（p<q）a[p]=a[q]（p<q），那麼小數點後第 pp 位到第 q−1q−1 位這一段就可以視為一 個循環節。 暴力計算數列 aa，找到第一個與前面重複的項，就可以找到最短循環節了。 這個重複的項前面的部分導出混循環部分。 如果最早在 pp 處計算到 a[p]=0a[p]=0，那麼原分數就是一個小數點後有 p−1p−1 位的有限小數。 以上便是 50 分的解法。
50分解法還很容易了解，但是接下來的100分做法就真的很難了解了。。。（也許是我太菜了吧）
下面我們對 aa 數列的性質做一些讨論。 如果 gcd(B,K)=1gcd(B,K)=1，對于任意的 ii 都有 gcd(a[i],B)=1gcd(a[i],B)=1。 設 K′K′ 為 KK modmod BB 時的乘法逆元，即 KK′KK′ modmod B=1B=1。由乘法逆元的性質 K′K′ 存在且唯一。 假設最早出現重複的位置是 a[p]=a[q](p<q)a[p]=a[q](p<q)。 如果 pp ≠ 11，那麼 a[p−1]=K′×a[p]a[p−1]=K′×a[p] modmod B=K′×a[q]B=K′×a[q] modmod B=a[q−1]B=a[q−1]。 也就是出現了更早的重複，與題設沖突。是以顯然有 p=1p=1。 這時，顯然原分數是一個純循環小數，且最短循環節長度是 q−1q−1。 設 x=q−1x=q−1。顯然 a[q]=a[1]×Kxa[q]=a[1]×Kx modmod B=a[1]B=a[1]，于是 KxKx modmod B=1B=1。 這就轉化成了求 KK modmod BB 的階的問題了。 由歐拉定理 Kphi(B)=1(Kphi(B)=1(modmod B)B)，由階的性質 x|phi(B)x|phi(B)。 我們可以将 phi(B)phi(B) 分解素因數，并初始化 x=phi(B)x=phi(B)。 之後考慮 phi(B)phi(B) 的每個素因數 pp。如果 K(x/p)=1(K(x/p)=1(modmod B)B)，就 x←xpx←xp，并繼續試除 pp。 否則轉下一個素因數。這樣就可以求出 KK modmod BB 的階了，這就是最短循環節的長度。 如果 gcd(B,K)>1gcd(B,K)>1，那麼 gcd(a[2],B)>1gcd(a[2],B)>1。設 gcd(a[2],B)=ggcd(a[2],B)=g，不難發現對于任意的 i≥2i≥2，有 g|(a[i],B)g|(a[i],B)。 不妨設 B′=BgB′=Bg，a′[i]=a[i]g(i≥2)a′[i]=a[i]g(i≥2)。 若此時 gcd(B′,K)=1gcd(B′,K)=1，就轉化為了上面的情況。否則繼續這個過程。 如果上面的轉換進行了 TT 次，由于 a[1]a[1] 到 a[T]a[T] 與後面 aa 數列的循環無關。 卡一下範圍便會知道循環節的最後一個數字與混循環部分最後一個數字一定不相等。 于是原分數的混循環長度就是 TT 了。 特殊地，如果在 TT 次轉換之後得到的最後一個 B=1B=1，那麼之後 aa 數列的值全為 0。這時 我們可以斷言原分數是一個小數點後有 TT 位的有限小數。 以上便是 100 分的做法。
好吧這麼多我知道沒人會看