"Все, Степан! Ти мене дістав!"#82

"Все, Степан! Ти мене дістав!" (Editorial)

Степан лопає бульбашки в моменти часу t_1, 2t_1, 3t_1, \ldots, а його товариш — у моменти t_2, 2t_2, 3t_2, \ldots

Викладач обернеться в перший момент, коли обидві бульбашки лопнуть одночасно, тобто в перший спільний момент цих двох послідовностей. Це число має ділитися і на , і на , а найменше таке додатне число — це найменше спільне кратне:

\mathrm{lcm}(t_1, t_2) = \frac{t_1 \cdot t_2}{\gcd(t_1, t_2)}.

Найбільший спільний дільник знаходиться алгоритмом Евкліда за .

Головна технічна пастка — переповнення: добуток t_1 \cdot t_2 може бути значно більшим за кожен зі співмножників. Тому рахуйте у порядку t_1 / \gcd(t_1,t_2) \cdot t_2 — спочатку ділення, потім множення — і використовуйте 64-бітний тип.