累乗剰余のテスト - 西尾泰和のはてなダイアリー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うん。正しい値
