b432: 趣味加分
Tags : 數論基礎
Accepted rate : 16人/19人 ( 84% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-07-06 23:03

Content

背景

廖氏如神 (pcsh710742) 在作業中遇到一題,用手算會算到天昏地暗,而問題是這樣子的:

$$ a^{13337} \equiv n \mod 2^{64} $$

其中 $n= 2015 + 2 \times (\text{The last 2 digit of your student ID number})$,請找到 $a < 2^{64}$ 的其中一組解。

問題描述

模數 $2^{64}$ 看起來不大,但對於 Ghz 為 CPU 運算速度單位的電腦而言還是要跑非常久的。因此將問題簡化:

$$ a^{23333} \equiv n \mod 2^{20} $$

現在給予一個 $n$,請求出一組 $a$,測資中保證答案唯一。

 

Input

多組測資,每一組測資一行一個整數 $n$,其中 $0 \le n < 2^{20}$。

Output
每組測資輸出一行,輸出一個符合的 $a$。
Sample Input #1
268275
888817
89215
63495
976477
Sample Output #1
387
817
639
487
909
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (80%): 1.0s , <1M
Hint :

請設計可以擴充到 $2^{64}$ 的代碼, 因為生測資的緣故,無法提供 special judge 請多多見諒。用暴力法是可以通過的。

Tags:
數論基礎
出處:
[管理者:
morris1028 (碼畜)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」