ABC131 C - Anti-Division

AtCoder Python3

備忘録

問題

atcoder.jp

回答

import sys
import os
import fractions

MOD = 10 ** 9 + 7


def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    A, B, C, D = list(map(int, sys.stdin.readline().split()))
    E = B - A + 1

    ret = 0
    ret += B // C
    ret += B // D
    ret -= (A - 1) // C
    ret -= (A - 1) // D
    ret -= B // lcm(C, D)
    ret += (A-1) // lcm(C, D)
    print(E - ret)


if __name__ == '__main__':
    main()

考え方

対象となる整数の数(B-A+1)から割り切れる整数の数を引くことで、
答えを求めることが出来る。

例えば、下記のようなinputの場合、

10 40 6 8

A = 10, B = 40, C = 6, D = 8とすると、

  • 対象となる整数が10 ~ 40の31個(E = B - A + 1)
  • 40以下の整数を対象に、6で割り切ることが出来る整数の数は40 // 6で6個(B // C)
    • そのうち、対象外の9以下の整数を6で割り切ることが出来る整数の数は9 // 6で1個((A - 1) // C)
      • つまり、対象となる整数10 ~ 40の31個のうち、6で割り切ることが出来る整数の数は5個(6 - 1)
  • 40以下の整数を対象に、8で割り切ることが出来る整数の数は40 // 8で5個(B // D)
    • そのうち、対象外の9以下の整数を8で割り切ることが出来る整数の数は9 // 8で1個((A - 1) // D)
      • つまり、対象となる整数10 ~ 40の31個のうち、8で割り切ることが出来る整数の数は4個(5 - 1)
  • 40以下の整数を対象に、6と8の最小公倍数24で割り切ることが出来る整数の数は40 // 24で1個(B // lcm(C, D))
    • そのうち、対象外の9以下の整数を6と8の最小公倍数24で割り切ることが出来る整数の数は9 // 24で0個((A-1) // lcm(C, D))

以上の計算を元に、
対象となる整数の数から、
6で割り切ることが出来る整数の数を減算、
8で割り切ることが出来る整数の数を減算、 6と8で割り切ることが出来る整数の数を減算することで、 以下のように、
31 - ((6 - 1) + (5 - 1) - (1 + 0)) = 23 対象の整数の数は23個と求めることが出来る