MITM в задаче о числах из 1 и 2, делящихся на M
Материал из Algocode wiki
Версия от 21:05, 6 мая 2020; Глеб (обсуждение | вклад)
Задача
Надо найти количество чисел $ < 10^{30}$ из 1 и 2, делящихся на $M, 1 < M < 10^6$
Решение
Переберем левую часть - запишем массив $cnt_{x}$ - количество чисел, дающих остаток $x$ при делении на $M$. Затем переберём также правую часть, пусть правая часть дает остаток $x$, тогда надо просто прибавить к ответу $cnt_{M - x}$
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin