Abst
- ABC 131 C問題 Anti-Division (300点)をpythonで解きました。
問題
- [A,B]の整数のうち、CでもDでも割り切れないものの個数を求める。
atcoder.jp
方針
- [A,B]の個数という問題なので、 [0,B]の個数から [0,A-1]の個数を引く ことで答えを求める。
- CでもDでも割り切れない数の個数は、
(Cで割り切れる数)+(Dで割り切れる数)-(CかつDで割り切れる数)
を全体から取り除くことで求めることができる。
- CかつDで割り切れる数は、言い換えると CとDの最小公倍数で割り切れる数 となる
回答
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
def gcd(a, b):
"""
最大公約数を求める
"""
if a < b:
a, b = b, a
while b:
a, b = b, a % b
return a
def lcm(a, b):
"""
最小公倍数を求める
"""
return a*b//(gcd(a, b))
def calc_num(n, C, D):
"""
0~Nまでで、C or Dで割り切れない数の個数
"""
div_C = n//C
div_D = n//D
div_CD = n//(lcm(C, D))
return n-div_C-div_D+div_CD
def solve():
A, B, C, D = map(int, input().split())
return calc_num(B, C, D)-calc_num(A-1, C, D)
print(solve())
終わりに
- 本番では、[A,B]での個数を直接求めようとして、テストケースの最後の一つだけWAになって、解けませんでした。
- #[A,B] = #[0,B]-#[0,A-1]の考えを忘れないようにしていきたい。(反省)(#は num of の意味)