atcoder.jp
問題
- 整数N,M,Kが与えられるよ
- NとMのうち、どちらか一方のみで割り切れる数のうち、小さい方からK番目のものを教えてね！
成約
- $1 \leq N,M \leq 2\times 10^{8}$
- $1 \leq K \leq 10^{10}$
思考
- とりあえず、最小公倍数＝1周期で、サイクルが作られる…ことはわかって…
- 最小公倍数＝NとMの両方で割り切れる一番小さい数
- これは正直どうでもよかった
- 整数Xが与えられた時に、X以下の正の整数で、NとMのどちらか一方のみで割り切れる数はいくつ？
- これはすぐ言えることに気がつくべきだった…
- NとMのどちらか一方でのみ割り切れる数 ＝ Nで割り切れる数の個数(X//N) + Mで割り切れる数の個数(X//M) - 2 * 最小公倍数で割り切れる数の個数(X//lcm)
- 上の判定がO(1)でできる
- 後は、Xが増えれば増える程、「どちらか一方のみで割り切れる数」は単調に増加するので…
- うまいこと計算一発系なのかなぁ…と式を手元でコネコネしてみたり、周期で色々計算してたけど上手く纏めきれず…（敗因）
- 最小公倍数！が見えて、数学問題だと思いこんでしまったのが良くなかった…反省…
- Tips：K番目がほしい！Kの制約が超絶大きい！→二分探索
- 本番のやり方でも、list作成しなかったら？通る？らしい…？？？ :TODO
コード
import math
N,M,K = map(int,input().split())
lcm = math.lcm(N,M)
def is_ok(arg):
return arg//N + arg//M - 2*(arg//lcm) >= K
ng = 0
ok = 10**19
def meguru_bisect(ng, ok):
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_ok(mid):
ok = mid
else:
ng = mid
return ok
print(meguru_bisect(ng, ok))
