На эту неделю подготовили тренировочный контест по базовой теории чисел.

В этой подборке собраны задачи на НОД, НОК, алгоритм Евклида, взаимную простоту, диофантовы уравнения, делимость, обратный элемент и работу с остатками. Это хороший набор для тех, кто хочет закрепить математическую базу, которая часто встречается в олимпиадном программировании и помогает быстрее видеть структуру задачи.

В контест вошли задачи:

• Загоны для скота — https://judje.olprog.ru/problem/livestockpens
• Общий ритм барабанов — https://judje.olprog.ru/problem/drumrhythm
• Когда автобусы встретятся — https://judje.olprog.ru/problem/busmeeting
• Сокращённый рецепт — https://judje.olprog.ru/problem/simplifiedrecipe
• Совместимые шестерёнки — https://judje.olprog.ru/problem/compatiblegears
• Платёж двумя жетонами — https://judje.olprog.ru/problem/twotokenpayment
• Лампы вдоль провода — https://judje.olprog.ru/problem/lampsonwire
• Балансировка магических кристаллов — https://judje.olprog.ru/problem/crystalbalance
• Точная дозировка зелья — https://judje.olprog.ru/problem/exactdose
• Подбор обратного ключа — https://judje.olprog.ru/problem/inversekey
• Шифр-замок — https://judje.olprog.ru/problem/cipherlock
• Невозможные суммы монет — https://judje.olprog.ru/problem/impossiblecoinsums
• Закупка двух типов товаров — https://judje.olprog.ru/problem/twogoodspurchase
• Совмещение календарей — https://judje.olprog.ru/problem/calendarmerge
• Точки на координатной сетке — https://judje.olprog.ru/problem/latticepairs
• Согласование расписаний — https://judje.olprog.ru/problem/schedulealignment

Этот контест подойдёт тем, кто хочет:

• уверенно закрепить НОД и алгоритм Евклида;
• научиться видеть задачи на НОК и совместные периоды;
• потренировать взаимную простоту и сокращение отношений;
• разобраться с простыми диофантовыми уравнениями;
• начать увереннее работать с обратными элементами и остатками.

Во время решения полезно каждый раз отдельно проговаривать:

• где в задаче появляется делимость;
• нужен ли здесь НОД или НОК;
• можно ли свести условие к линейному диофантову уравнению;
• требуется ли проверка существования решения;
• не возникает ли переполнение при умножении больших чисел;
• какие ограничения подсказывают нужную сложность.

Рекомендуем решать подборку в формате мини-контеста: выделить себе 2–3 часа, сначала пройти задачи на прямое применение НОД и НОК, а затем перейти к более содержательным задачам на уравнения, остатки и обратные элементы. После контеста полезно отдельно выписать для каждой задачи, какая математическая идея была ключевой.

Удачи в решении!

Ждём ваши результаты, вопросы и впечатления от задач.