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

from library-checker-problems.

0 2 4

で 1 と言いませんか

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

from library-checker-problems.

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

from library-checker-problems.

#78

from library-checker-problems.

2 <= m -> 1 <= m

from library-checker-problems.

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

from library-checker-problems.

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

from library-checker-problems.

問題概要

• 問題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

from library-checker-problems.

バグ確認！

from library-checker-problems.

0^0が未定義　1です

from library-checker-problems.

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

from library-checker-problems.

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

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

from library-checker-problems.