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