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