Теория чисел (НОД, НОК, остатки) на Python: как решать + 17 задач с проверкой

Теория чисел в олимпиадах — это задачи про делимость, НОД (наибольший общий делитель), НОК (наименьшее общее кратное) и остатки по модулю. Она встречается в сюжетах про «срабатывания каждые m минут», упаковки по k штук, повторяющиеся циклы, последнюю цифру результата, ключи/фонари на равных расстояниях.

Как распознать, что здесь нужна именно она:

• в условии есть слова «кратно», «делится», «остаток», «последняя цифра», «каждые m», «повторяется через…»;
• нужно найти первый момент, когда два расписания совпадут (или понять, что не совпадут);
• ограничения большие (до 1e9), значит перебор по времени/числам не пройдёт;
• требуется ответ в 64-битном диапазоне (намёк на НОК и большие произведения).

Суть приёма: мы переводим сюжет в уравнения вида t кратно m и t даёт остаток r по модулю p. Дальше используем НОД: он показывает, какие остатки вообще достижимы, а НОК (или решение сравнений) — как найти минимальное подходящее t. Это ускоряет решение, потому что вместо поиска по всем t мы делаем несколько операций Евклида (НОД) и аккуратные вычисления.

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

• вспомнить алгоритм Евклида для НОД и как из него получить НОК: lcm(a,b) = a/ gcd(a,b) * b (с защитой от переполнения);
• научиться проверять существование решения для условий вида t ≡ r (mod p) вместе с t кратно m;
• тренировать «перевод текста в математику»: расписания → кратности и остатки;
• держать в голове 64-битные типы и порядок вычислений (делить до умножения).

Ниже — задачи с автопроверкой и разбором подхода по НОД/НОК и остаткам.