python 10の9乗足す7の余り

Question

質問

AtCoderで10の9乗足す7の余りで答えを出す問題が多々ありますが、以下の書き方で正解と不正解に分かれてしまい、なぜこうなるのかを教えてください。

#sumには合計値が入っていいる
print(sum%(10**9+7))　#AC
print(int(sum%(1e9+7)))　#WA

どちらも10の9乗足す7で意味は同じはずなのですが、浮動小数点などでオーバーフローしているのが原因なのでしょうか。

Answer 1

1e9はfloat(浮動小数点)なので、sumもfloat化されて計算されますが、このsumの値がものすごい大きい数の場合、float化すると小さい桁が情報落ちし、正確ではなくなります。(今回の1e9側ももっと大きければ同様の現象が発生します。)

>>> float(43248975438843428)
4.324897543884342e+16   #最後の8が情報落ち

なので、最終的に計算結果が異なってきます。

>>> 43248975438843428 % (10**9+7)
136100603

>>> int(43248975438843428 % (1e9+7))
136100599

Answer 2

浮動小数点などでオーバーフローしているのが原因なのでしょうか。

オーバーフローではありませんが、浮動小数点数として扱われると有効桁を超える範囲の演算では結果が変わってきます。

sum = 123456789012345678

f = sum*1e1
print(type(f), f)# <class 'float'> 1.2345678901234568e+18
i = sum*1
print(type(i), i) #<class 'int'> 123456789012345678

print(sum%(10**9+7))    # 148148162
print(int(sum%(1e9+7))) # 148148164