筆者はレート800前後の茶～緑コーダ
ABC341のD問題を解いていく
実装コード
X以下のM,N片方のみで割り切れる数で計算して二分探索するようだ。
X以下の数でX がM,Nで割り切れる数の個数はそれぞれfloor(X/N),floor(X/M)
これを足し合わせると N と M の両方で割り切れる数を二重に数えてしまうため、
XがN,Mのどちらでも割り切れる数の個数
floor(X/lcm(N,M)), ※lcm:最小公倍数
の2倍を引いて、N,M片方のみに割り切れる数の個数を算出する。
つまり以下の式、
floor(X / N) + floor(X / M) - 2 * floor(X / lcm(N, M))
この値が K 個以上になる最小の X を、二分探索で求める。
main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)
def gcd(a, b):
while b:
a, b = b, a % b
return a
def lcm(a, b):
return a * b // gcd(a, b)
MAX = int(2e18)
def main():
N, M, K = rLI()
L= lcm(N,M)
l= 0
r= MAX
while r-l>=2:
m = (l+r)//2
x = m//N+m//M-2*(m//L)
err(f"{m} {x}")
l,r= (l,m) if x >= K else (m,r)
err(f"{l},{r}")
print(r)
if __name__ == '__main__':
main()
感想
数学寄りの問題で理解するのに苦労したが、
実装は典型的な二分探索だったので、こういうのを解けるようになりたい。