MITM в задаче о числах из 1 и 2, делящихся на M

Материал из Algocode wiki
Версия от 21: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