[問題案]k-th root

[yosupo06]

a,n, mが与えられる

x^n = a(mod m)を満たすxを求める

[hos-lyric]

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 まででケースが少ないと離散対数で解けてしまうので云々

[Maruoka842]

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 k2 \vdots p{Q} a{Q} k{Q}

制約

Q < 5e3 p_i < 1e9 a_i < p_i

[yosupo06]

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

[Maruoka842]

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

[yosupo06]

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

[Maruoka842]

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

[yosupo06]

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

[Maruoka842]

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