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

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

Вторая часть подборки посвящена префиксным суммам: быстрым суммам на отрезках, подотрезкам с заданной суммой, двумерным префиксам и разностным массивам. Это одна из самых полезных техник для задач на массивы, запросы и таблицы.

Диофантовы уравнения и теория чисел

• Линейное уравнение — https://judje.olprog.ru/problem/linearequation
• Проверка делимости — https://judje.olprog.ru/problem/divisibilitychecks
• Наибольший общий делитель — https://judje.olprog.ru/problem/gcdpair
• НОД массива — https://judje.olprog.ru/problem/gcdarray
• Расширенный алгоритм Евклида — https://judje.olprog.ru/problem/extendedeuclid
• Линейное сравнение — https://judje.olprog.ru/problem/linearcongruence
• Минимальное неотрицательное решение — https://judje.olprog.ru/problem/minimalnonnegsolutio
• Обобщённая китайская теорема об остатках — https://judje.olprog.ru/problem/crtgeneral

Префиксные суммы

• Сумма массива — https://judje.olprog.ru/problem/arraysum
• Сумма префикса фиксированной длины — https://judje.olprog.ru/problem/prefixsumk
• Сумма на отрезке — https://judje.olprog.ru/problem/rangesumqueries
• Сумма чётных и нечётных позиций — https://judje.olprog.ru/problem/oddevenprefix
• Количество подотрезков с заданной суммой — https://judje.olprog.ru/problem/subarrayswithsums
• Сумма на прямоугольнике в матрице — https://judje.olprog.ru/problem/matrixrectsum
• Максимальная сумма подотрезка длины k — https://judje.olprog.ru/problem/maxwindowsumk
• Покраска прямоугольников в матрице — https://judje.olprog.ru/problem/rectupdatespointquer

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

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

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

• где появляется равенство вида a * x + b * y = c;
• нужно ли здесь найти НОД;
• делится ли правая часть на НОД коэффициентов;
• требуется ли одно решение или все решения в некотором диапазоне;
• нужно ли аккуратно работать с остатками по модулю.

А в задачах на префиксные суммы стоит отдельно отслеживать:

• какой массив префиксов нужно построить;
• как выразить ответ на отрезке через разность двух префиксов;
• нужна ли отдельная обработка чётных и нечётных позиций;
• требуется ли двумерный префикс;
• не превращается ли задача в разностный массив с последующим восстановлением значений.

Рекомендуем решать подборку в два захода: сначала пройти математический блок, а затем переключиться на префиксы. Так проще не смешивать разные техники и лучше увидеть, какие идеи повторяются внутри каждой темы. Удачи в решении!