Atcoder ABC 131 C問題

Question

前提・実現したいこと

Atcoder ABC 131 C問題

以下のコードを提出すると3個だけWAと表示されます。いくら考えても誤っている部分がわからず困っています。

問題文
整数 A,B,C,D が与えられます。A 以上 B　以下の整数のうち、C でも D でも割り切れないものの個数を求めてください。

制約
1≤A≤B≤10^18
1≤C,D≤10^9
入力はすべて整数である

URL
https://atcoder.jp/contests/abc131/tasks/abc131_c

発生している問題・エラーメッセージ

ある入力に対して以下のコードで導き出される答えが間違っている。

該当のソースコード

import math

a,b,c,d = map(int, input().split())

lcm = c*d / math.gcd(c,d)

def num(i):
  ans = int(b/i) - int(a/i)
  if a % i == 0:
    ans +=1
  return ans

lcm_num = num(lcm)

cd_num  = num(c) + num(d)

num = cd_num - lcm_num

print(b-a+1-num)

試したこと

AB範囲内のC,D,最小公倍数のそれぞれの倍数の個数を計算し解答を求めようとしました。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Comments

[maisumakun]

思いついただけで検証していないのですが、

・A=B
・ CやDがBよりも大きい
・C=1あるいはD=1
・C=D

などの特殊な場合について、考慮漏れがあるのかもしれません。

Answer 1

Pythonでは'/'を使って割り算をすると浮動小数点での計算になるので誤差が出ます。
桁数が大きい数で int(x / y) が必要な場合は x // y を使ってください。lcm についても結果は整数になりますが、今のままでは浮動小数点での表現になるので大きな値になる場合に誤差が出ます。

Comments

[Mmaple]

ご指摘の通りに直したら通りました。ありがとうございます。浮動小数点を意識したことがなかったので助かりました。