[問題案]Discrete Logarithm(discrete_logarithm_mod)

[yosupo06]

Tケース

x, y, mが与えられる。x^k = y (mod m)なるkのうち、最小を答えよ(存在しない場合-1)

• 1 <= T <= 100?
• 1 <= m <= 10^9
• 0 <= x, y < m

[yosupo06]

2 <= m -> 1 <= m

[yosupo06]

sqrt(10^9) logで100ケースも動くか？

[hos-lyric]

unordered_map なら log が消えるみたいな主張 (うーん)

[hos-lyric]

φ(m) がいろんな素因数で割れるとき速い，みたいな方法はあるので，複数ケースで時間計るのは要注意という話があります https://ja.wikipedia.org/wiki/安全素数 https://en.wikipedia.org/wiki/Pohlig–Hellman_algorithm

[yosupo06]

問題概要

• 問題ID: discrete_logarithm
• 問題名: Discrete Logarithm

Tケース与えられる。

x, y, mが与えられる。x^k = y (mod m)なるkのうち、最小を答えよ(存在しない場合-1)

入力

T
x y m
x y m
:
x y m

出力

各行に求めたもの

制約

1 <= T <= 100?(速度見ながら調整) 1 <= m <= 10^9 0 <= x, y < m

[hos-lyric]

0 2 4

で 1 と言いませんか

ちゃんと読んでないけど m が素数じゃないとき全然ダメな気がします

[yosupo06]

バグ確認！

[yosupo06]

0^0が未定義　1です

[yosupo06]

巡回に入るまでが長いケース、x = 2でmod = 2^29など

[yosupo06]

もっと大きい制約で解けた　どうすっかな

https://loj.ac/problem/6542 http://elliptic-shiho.hatenablog.com/entry/2016/12/02/051931

[beet-aizu]

個人的には両方ほしいです　実装量がかなり変わる奴はICPCでは使い分けるので（最小有向全域木のO(VE) とO(E log V)とか

[yosupo06]

#78