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