Расклейка афиш

Первую подзадачу ($$$n \le 10^{5}$$$) можно решить с использованием перебора, например, так:

[language=Python, frame=single]
n = int(input())
a = int(input())
b = int(input())
ans = 0
for i in range(1, n + 1):
if i % a == 0 or i % b == 0:
ans += 1
print(ans)

Вторую подзадачу ($$$a=2$$$) можно решить с использованием разбора двух случаев.

Если $$$b$$$ тоже чётное, то при втором проходе Воробьянинов не расклеит новых афиш.

Если $$$b$$$ — нечётное, то каждый второй дом, на который нужно наклеить афишу на втором проходе, уже будет иметь афишу (так как сумма двух нечётных чисел всегда чётна). Чтобы найти число подходящих номеров поделим $$$n$$$ на $$$b$$$, а потом полученное число поделим на 2 с округлением вверх.

[language=Python, frame=single]
ans = n // 2
if b % 2:
ans += (n // b + 1) // 2
print(ans)

Для решения задачи на полный балл нужно сложить количество афиш, наклеенных Воробьяниновым при первом проходе, и количество афиш, которые он наклеит при втором проходе так, если бы первого прохода не было. Мы дважды посчитали дома, номера которых делятся нацело и на $$$a$$$, и на $$$b$$$.

Посчитаем количество номеров домов, которые делятся и на $$$a$$$, и на $$$b$$$. Первое такое числоа должно делиться нацело и на $$$a$$$ и на $$$b$$$ и быть наименьшим возможным. Согласно определению, это наименьшее общее кратное $$$a$$$ и $$$b$$$. Его можно найти через каноническое разложение обоих чисел на простые множители или через наибольший общий делитель (который в свою очередь находится с помощью алгоритма Евклида):

$$$$$${\text{НОК}}(a, b) = \frac{a \times b}{\text{НОД}(a, b)}$$$$$$

Итоговое количество вычитаемых чисел составит $$$n$$$ // ($$$a$$$ * $$$b$$$ // НОД($$$a$$$, $$$b$$$))

[language=Python, frame=single]
def gcd(n, m):
if m == 0:
return n
return gcd(m, n % m)

n = int(input())
a = int(input())
b = int(input())
ans = n // a + n // b - n // (a * b // gcd(a, b))
print(ans)