累乗剰余のテスト

topcoder

TopCoderとかでたまに出る「値が巨大になるのでNであまりを取って答えてね」のためにあまりを取る階乗とかを作って用意しておいた方がいいのかなー、なんてことをid:suztomoに話したらこんなサイトを教えてもらった: Spaghetti Source - べき剰余

で、今読んでいたんだけど、これって x * x がIntの上限を超えるときに powMod(x, 2) されても大丈夫なんだろうか。


というわけで試してみた。

int main(){
  Int x = 1 << 30;
  DP(x);
  DP(x * x);
  DP(powMod(x, 2, 10));
  DP(((x % 10) * (x % 10)) % 10);
}

結果

x: 1073741824
x * x: 0
powMod(x, 2, 10): 0
((x % 10) * (x % 10)) % 10: 6

うん。正しい値は6なのに0が返ってしまうね。

その後の流れ

  • 1: 自分で実装しようと考える
  • 2: 何度も繰り返し呼ばれるわけだから計算結果をキャッシュする方がいいんじゃないかと考える
  • 3: x=1, 2, 4, 8, 16, ... の時の結果を先に作って持っておいてもO(log(N))だよなと考える
  • 4: 一回計算してグローバル領域に持っておけばいいんじゃないかと考える
  • 5: ふとそれでいいのか確認したことがなかったことに気づき、TopCoderでグローバル領域にカウンタを持って10回目のテストでfailするようなコードをシステムテストにかけてみる
  • 6: なんとfailしない！グローバル領域にキャッシュしてテストケース間で使い回しをする戦略は使えない
  • 7: ならコンパイルタイムに計算するしかない。
  • 8: しばらく考えてうまくいかなかったので専門家(@earth2001y)に聞こうと思ってTwitterでやりたいことの説明を書く
  • 9: 送信前に「いや、Mが固定なんだったらそもそもコンパイル時に向こうで計算する必要すらないだろ」と気づく
  • 10: 勘違いだったと気づく(「xが固定なら」の間違い)
  • 11: でも少なくとも素数テーブルは持っていても損はないよな