Арифметика и формулы (O(1)) на Python: как решать + 11 задач с проверкой

Арифметика и формулы (O(1))

Это набор приёмов, когда ответ можно вычислить «в лоб» по нескольким действиям: делениям, остаткам, НОД/НОК, разностям и аккуратному учёту границ. Такие задачи часто маскируются под время (будильники, расписания), периодические события (реклама каждые a и b секунд), цены «по слоям», подсчёт кругов/шагов и балансы, где симуляция слишком медленная.

Как распознать, что нужна O(1)-формула:

• ограничения большие (до 10^9 и выше), а наивный цикл по всем секундам/дням/элементам явно не пройдёт;
• в условии встречаются слова «каждые a», «каждый b», «за первые n», «сколько раз», «сколько целых t подходит»;
• нужно посчитать количества кратных, отрезки времени, полные периоды, или объединение двух условий «A или B».

Суть приёма: вместо перебора мы считаем, сколько раз событие случится по каждому правилу, и корректируем пересечения. Например, «кратно a или кратно b» считается как: n/a + n/b - n/lcm(a,b), где lcm — наименьшее общее кратное, а пересечение убираем, чтобы не посчитать дважды. Это даёт мгновенный ответ и проходит большие n.

С чего начать учиться:

• тренируй целочисленное деление и работу с границами (что происходит с моментом 0, включительно/исключительно);
• выучи НОД (gcd) и НОК (lcm) и как считать lcm(a,b) = a/gcd(a,b)*b без переполнения;
• используй принцип включений-исключений для «или» и «оба»;
• проверяй на маленьких примерах и крайних случаях (a=1, a=b, n<a);
• помни про 64-битные типы, если промежуточные значения больше 2^31-1.

Ниже — задачи с автопроверкой и разбором подхода: от простых формул до аккуратных случаев с пересечениями и большими числами.