yukicoder 1350 2019-6problem
愚直に列挙していくと間に合いそうにない.
ここで二分探索の適用を考える. すると, 答えは
$ K \leq \lfloor \frac{x}{A} \rfloor + \lfloor \frac{x}{B} \rfloor - \lfloor \frac{x}{lcm(A,B)} \rfloor
なる最小の
$ x
となる. よって
$ O(log M)
(
$ M
はとりうる答えの最大値)でこの問題を解くことができた.
実装例:
https://yukicoder.me/submissions/606329