Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[問題案]Discrete Logarithm(discrete_logarithm_mod) #28

Open
yosupo06 opened this issue Sep 12, 2019 · 12 comments
Open

[問題案]Discrete Logarithm(discrete_logarithm_mod) #28

yosupo06 opened this issue Sep 12, 2019 · 12 comments

Comments

@yosupo06
Copy link
Owner

@yosupo06 yosupo06 commented Sep 12, 2019

Tケース

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

  • 1 <= T <= 100?
  • 1 <= m <= 10^9
  • 0 <= x, y < m
@yosupo06 yosupo06 added this to 精査待ち in 問題リスト Sep 12, 2019
@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Sep 12, 2019

2 <= m -> 1 <= m

@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Sep 12, 2019

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

@yosupo06 yosupo06 moved this from 精査待ち to 作業待ち in 問題リスト Sep 13, 2019
@hos-lyric

This comment has been minimized.

Copy link
Contributor

@hos-lyric hos-lyric commented Sep 16, 2019

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

@hos-lyric

This comment has been minimized.

Copy link
Contributor

@hos-lyric hos-lyric commented Sep 16, 2019

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

@yosupo06 yosupo06 changed the title [問題案]discrete logarithm(discrete_logarithm_mod) [問題案]Discrete Logarithm(discrete_logarithm_mod) Sep 27, 2019
@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Sep 27, 2019

問題概要

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

yosupo06 added a commit that referenced this issue Oct 15, 2019
@yosupo06 yosupo06 self-assigned this Oct 15, 2019
yosupo06 added a commit that referenced this issue Oct 15, 2019
add discrete_logarithm_mod #28
@hos-lyric

This comment has been minimized.

Copy link
Contributor

@hos-lyric hos-lyric commented Oct 15, 2019

0 2 4

で 1 と言いませんか

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

@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Oct 15, 2019

バグ確認!

@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Oct 15, 2019

0^0が未定義 1です

@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Oct 15, 2019

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

@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Oct 16, 2019

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

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

@beet-aizu

This comment has been minimized.

Copy link
Contributor

@beet-aizu beet-aizu commented Oct 16, 2019

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

@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Oct 16, 2019

#78

@yosupo06 yosupo06 removed their assignment Oct 17, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
問題リスト
  
作業待ち
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
3 participants
You can’t perform that action at this time.