NASU41 / AtCoderLibraryForJava

Creative Commons Zero v1.0 Universal

78 stars 23 forks source link

Closed uwi closed 4 years ago

uwi commented 4 years ago

33

原典とコードをほぼ同じに

mの制約をintに
&&でつなぐassertionは複数行のほうが引っかかったときの原因がすぐにわかるのでそうする
m=1を場合分け(x=1%mとしてもよい)
xの初期値をsafe_modで求める
%2, /2を&1, >>>=1として2%高速化(ローカル測定)
AOJ/NTL_1_B, SPOJ/MODPOW, SPOJ/FASTPOW でverified. ただしどれもpow_modの引数の範囲を網羅できているわけではない。

m1kit commented 4 years ago

mがint型なら戻り値もint型にできると思うのですが，どちらが良いのでしょうか...? 個人的には戻り値がintでないと困るケースはほとんどないしどちらでもよいと思いますが，Javaだと配列の添え字にはintしか突っ込めない等の事情もあるので一応意見がききたいです．

uwi commented 4 years ago

制約的にはintで良いですね。

自分のライブラリだと、この周囲に乗算があった場合、longでいたほうがキャストしなくて良いかな的なところがあります。

m1kit commented 4 years ago

確かに，pow_mod(x1, y1, m) * pow_mod(x2, y2, m) % mみたいなことをする機会の方が圧倒的に多いので，longの方が良いという気持ちになりました．ありがとうございます．