[問題案] Primitive Root

[SSRS-cp]

問題名: Primitive Root 問題 ID: primitive_root

https://37zigen.com/primitive-root/

問題

$Q$ クエリ

$3$ 以上の素数 $P$ が与えられる。$P$ の原始根を $1$ つ求めよ。

制約

• $1 \leq Q \leq 100$
• $3 \leq P \leq 10^{18}$
• $P$ は素数

[SSRS-cp]

制約は #41 に合わせました

[NachiaVivias]

$10^{18}$ は不親切ではありませんか？ $2 \times 10^9$ だとたぶん試し割りでも間に合うようになって、それでできたなら整数型のランクを上げて Factorize と組み合わせればよいので、用意する問題は $P\leq 2\times 10^9$ のほうが便利になると思います。

[SSRS-cp]

なるほど 制約を下げておきます。

[yosupo06]

10^18で大丈夫です　試し割りをverifyしたい需要があるならばテストケースにp <= 2*10^9のみのテストケースも入れておく感じで