pythonで青くなるブログ

主に競プロのについての記事(日記的な)を書きます。現在atcoder水色,こどふぉ青色。python3使って、やってます。atcoder青くなりたい

ABC 131 Anti-Division

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の最小公倍数で割り切れる数 となる

    回答

# python template for atcoder1
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 の意味)