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

[問題案]Sqrt Mod(sqrt_mod) #27

Closed
yosupo06 opened this issue Sep 12, 2019 · 15 comments
Closed

[問題案]Sqrt Mod(sqrt_mod) #27

yosupo06 opened this issue Sep 12, 2019 · 15 comments

Comments

@yosupo06
Copy link
Owner

@yosupo06 yosupo06 commented Sep 12, 2019

Tケース

y, pが与えられる。x^2 = y (mod p)なるxを1つ求めよ(存在しない場合、-1)

  • 1 <= T <= 100,000
  • 2 <= p <= 10^9
  • 0 <= y < p
  • p is prime
@yosupo06 yosupo06 added this to 精査待ち in 問題リスト Sep 12, 2019
@hos-lyric

This comment has been minimized.

Copy link
Contributor

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

sqrt y じゃん (mod_sqrt か sqrt_mod でいいんじゃないかな)
すべて求めよでもいいと思う

@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Sep 12, 2019

p is prime忘れてた(ないと崩壊)

@yosupo06 yosupo06 changed the title [問題案]Sqrt x Mod(sqrt_x_mod) [問題案]Sqrt Mod(sqrt_mod) Sep 12, 2019
@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Sep 12, 2019

一つ -> 全て

@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Sep 12, 2019

やっぱり1つ出力にします、無すぎるので

yosupo06 added a commit that referenced this issue Sep 12, 2019
yosupo06 added a commit that referenced this issue Sep 12, 2019
add sqrt_mod #27
@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Sep 12, 2019

想定解めんどくて書かなかったらサンプル出力がない

@hos-lyric

This comment has been minimized.

Copy link
Contributor

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

y = 0 で example_00 が落ちる

ということはデータがよわい
(0, 1, -1 とランダムとかでいい気がするけど)
p = 2 とか入ってるのかな (見てない)

yosupo06 added a commit that referenced this issue Sep 12, 2019
@yosupo06 yosupo06 moved this from 精査待ち to 作業待ち in 問題リスト Sep 12, 2019
@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Sep 12, 2019

とりあえずcheckerだけ直しました

@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Sep 13, 2019

ケース生成が重過ぎる

@hos-lyric

This comment has been minimized.

Copy link
Contributor

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

問題一覧に表示されてない気がする
(どこを直せばいいのかわからないので報告でゆるして)

@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Sep 13, 2019

あぁ〜忘れてた〜

@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Sep 15, 2019

#61 でついでにy = 0も入ったので、いっかい閉じます

@yosupo06 yosupo06 closed this Sep 15, 2019
問題リスト automation moved this from 作業待ち to 作成済み Sep 15, 2019
@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Sep 27, 2019

テストケースが弱い?

@yosupo06 yosupo06 reopened this Sep 27, 2019
問題リスト automation moved this from 作成済み to 作業待ち Sep 27, 2019
@hos-lyric

This comment has been minimized.

Copy link
Contributor

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

今ので弱いかどうかはわからず…… (あとで眺めたい (希望))

ところで,わたしのやつ (Cipolla) は最悪 O(log p) だけど,有名な Tonelli–Shanks は p - 1 が 2 で割れるほど遅い (2 乗かかる) という話があり,これもやはり複数ケース要注意案件だったりする

@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Sep 27, 2019

弱いという報告を受けたの、sqrt(母関数)の方だった…

それはそうとしてTonelli-Shanksの最悪計算量は完全に忘れていたので、OK(結果論)

@yosupo06

This comment has been minimized.

Copy link
Owner Author

@yosupo06 yosupo06 commented Oct 16, 2019

p - 1が2で割れる、ということでmod 998244353 onlyを足しました

@yosupo06 yosupo06 closed this Oct 16, 2019
問題リスト automation moved this from 作業待ち to 作成済み Oct 16, 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
2 participants
You can’t perform that action at this time.