概要
以下の問題にて、math.floorの過信から、なかなかACを通せなかったので、その過程をまとめました。
ABC048 B問題
解き方の経緯
B問題だったので、大体全探索だろうと思い、
- 片っ端から%を用いて余りの判定、aとbの範囲内か判定する
という方法を考えましたが、a, b, xが10^18のオーダーなので、断念。
続いて、
- $a <= x*i <= b$を満たすiを繰り返し処理で探していく
という方法も考えましたが、xの大きさにより、こちらも計算量が膨大になる可能性があるため、断念。
最後に、
- aとbをxで割り、その差によって、条件を満たす個数を出す（累積和的なイメージ）
を考え、両端の処理だけ上手いことやれば、答えが出せということで実装していきました。
実装について
やっと本題です。何も考えず、両端をmath.floorとmath.ceilを用いて導こうとしていました。
import math
a, b, x = map(int, input().split())
# 条件の範囲の両端をそれぞれ求める
left = math.ceil(a/x)
right = math.floor(b/x)
# 条件を満たす数字をrangeの個数で求める
ans = len(range(left, right))
# 右端のみ、bがxで割り切れると個数が変わるので、判定
if b % x == 0:
ans += 1
print(ans)
しかし、以下の
input.txt
1 1000000000000000000 3
が
- 333333333333333311
（理想は全て3）となり、途方に暮れました。
ここで、色々と調べてみるとpythonのmath.floor/ceilではfloat型が用いられており、そのfloat型はCのdouble型を元に実装されていて、10進数だと上限が15桁ほどが限界らしい。
参考にしたpythonのドキュメント
参考にしたCの記事
ところがどっこい、pythonのint型には、上限がないため、精度の高い計算を行う場合は、できる限りint型を使った方が良いらしい。
ということで、math.floorから四則演算の//に変更した実装は以下です。
a, b, x = map(int, input().split())
# 値が切り捨てられている場合のみ、+1をする
left = a // x
if a % x != 0:
left += 1
right = b // x
ans = len(range(left, right+1))
print(ans)
結論
math.floor, math.ceilでは15桁くらいでオーバーフローが起きる。
（atcoderでは、これによってWAに…！！）
int型には上限がないため、桁数が多い場合には、通常の四則演算を用いよう！