[問題案]k-th root about library-checker-problems HOT 8 CLOSED

k-th log じゃなくて k-th root だよね (しかも n になってるし)

m が素数以外で解けるのかは知らない

x^k == a (mod p)
O(k^3 + k^2 log p) 系もあるけどここでやるのは p^(1/4) 系だよねたぶん
p が 10^9 まででケースが少ないと離散対数で解けてしまうので云々

from library-checker-problems.

O(p^{1/4+ε})だと下の制約で最悪ケース1secぐらいで丁度良いと思います。
pが合成数の場合の解法は考えたことないです。

問題概要

p_i, a_i, k_i について x^k=a_i (mod p_i) を満たすxを出力せよ。
ただし解が存在しなければ-1を出力せよ。

入力

Q
p_1 a_1 k_1
p_2 a_2 k_2
\vdots
p_{Q} a_{Q} k_{Q}

制約

Q < 5e3
p_i < 1e9
a_i < p_i

from library-checker-problems.

• (非本質ですが) https://judge.yosupo.jp/problem/sqrt_mod に合わせて Q -> T、a_i -> Yで、入力順はK, Y, P (かY, K, P) としたいです
• Pは素数でいいと思います
• 速度は測らないと謎ですが、そんなものな気がします

from library-checker-problems.

入力順、了解です。
Kの制約を忘れていました。
1<= K <= 1e9
のつもりでした。K=0を含めるかどうかはどうしましょうか。
X^K=1 mod Pの解にX=0,K=0を含めるかなど。

from library-checker-problems.

入れておいていいと思います -> K = 0

from library-checker-problems.

worst_caseでも100msで思ったより速いですね………

from library-checker-problems.

https://judge.yosupo.jp/submission/5840 出ちゃいけないものが出てます

from library-checker-problems.

解説です。
https://yukicoder.me/problems/no/981/editorial

from library-checker-problems.