Реклама по расписанию

Ты смотришь длинный ролик. Плеер умеет вставлять рекламу по двум независимым «будильникам»:

• первый срабатывает каждые a секунд,
• второй срабатывает каждые b секунд.

Если в одну и ту же секунду срабатывают оба, реклама всё равно показывается один раз.

Посчитай, сколько раз реклама покажется за первые n секунд просмотра (то есть в моменты времени 1, 2, ..., n). Момент времени 0 не учитывается.

Формат ввода Одной строкой даны три целых числа a b n.

Формат вывода Выведи одно целое число — сколько секунд t (1 ≤ t ≤ n) делятся на a или на b.

Ограничения

• 1 ≤ a, b, n ≤ 10^9
• В вычислениях могут встречаться значения больше 2^31−1 (как на олимпиадах), в частности при нахождении НОК.

Пример Ввод:

3 5 20

Вывод:

9

Пояснение: срабатывания в секундах 3, 5, 6, 9, 10, 12, 15, 18, 20 (в 15 оба сразу, но считается один раз).

Ключевое наблюдение: реклама показывается в секунды t, которые делятся на a или на b. Если t делится на оба, событие одно, значит такие секунды нельзя посчитать дважды.

Для этого подходит принцип включения-исключения:

• посчитать количество кратных a;
• добавить количество кратных b;
• вычесть количество кратных одновременно a и b.

«Одновременно кратные» — это кратные НОК(a, b). НОК удобно находить через НОД: lcm = a // gcd(a, b) * b. Важно делить до умножения, чтобы не получить лишнее переполнение в языках с 32-битным int (в Python всё равно безопасно, но привычка полезная).

План решения:

• Прочитать a, b, n.
• Найти g = gcd(a, b) обычным алгоритмом Евклида (пока b != 0).
• Посчитать l = a // g * b.
• Ответ: n // a + n // b - n // l.

Сложность: O(log(min(a, b))) по времени из-за НОД, память O(1).

Частая ошибка: вычитать n // (a*b) вместо n // lcm — это верно только когда a и b взаимно просты.