b435: 尋找原根
Tags : 數論基礎
Accepted rate : 19人/21人 ( 90% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-07-06 22:27

Content

原根(primitive root)是在數論中一個很重要的概念。

模$m$的原根(A primitive root modulo $m$)是一個正整數$g$,使得
\[g^{\phi(m)} \equiv 1 (\mathrm{mod}~m)\]

\[g^\gamma \not \equiv 1 (\mathrm{mod}~m)\]
對$1 \leq \gamma < \phi(m)$恒成立。

其中$\phi(m)$是歐拉(Euler)函數。

對於一個模$m$的原根$g$, 他的冪$g^0,g^1,\dots,g^{\phi(m)-1}$組成了模$m$的簡化剩餘系(a reduced system of residues modulo $m$)。

現在你的任務就是,給你一個質數模$p$,求出$p$的最小原根。 

Input
有若干筆測資。每筆測資占一行,只有一個質數$p(2 \leq p \leq 2,100,000,000)$。
Output
對每筆測資,輸出一個數字并換行,表示對應的$p$的最小原根。
Sample Input #1
2
3
5
7
Sample Output #1
1
2
2
3
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 3.0s , <1M
Hint :
約一萬筆測資。
Tags:
數論基礎
出處:
[管理者:
liouzhou_101 (王启圣)
]


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