wataru
@wataru
Разработчик на С++, экс-олимпиадник.

Можно ли быстрее чем за O(N) подсчитать сумму S(N,K,M) = sum i=0..N K*i%M?

Сразу скажу: это часть олимпиадной задачки. Там авторы удовлетворились и линейным наивным алгоритмом, но это единственная часть, которая делает все решение задачи линейным. Мне все кажется, что тут можно и за какой-нибудь логарифм все подсчитать, но додуматься не могу никак.

Мои наблюдения:
Можно найти GCD K и M, потом можно и то и другое поделить и дальше можно допустить, что k и m взаимнопросты.

Дальше, можно считать, что N < M. Потому что полные "круги" из-за взаимнопростоты K и M соберут все остатки по модулю M в перемешку и их можно подсчитать формулой M(M-1)/2. Останется только часть в конце длины N%M.

Можно перейти от модуля к делениям с округлениями вниз, воспользуясь формулой floor(a/b)*b = a - a%b, но как это использовать я не придумал.

Казалось бы, тут что-то вроде решения задачи Иосифа напрашивается - как-то хитро считать арифметическую прогрессию, пока k*i не перевалит за m. Есть сколько-то начальных позиций, куда k*i приземляется, делая полный оборот через m, и вот от этих точек арифметические прогрессии с шагом +k можно сложить за O(1). Проблема только в том, что часть этих прогрессий будет на 1 шаг длинее остальных. Вроде тут напрашивается какая-то рекурсия, но я не смог это формализовать.
  • Вопрос задан
  • 657 просмотров
Пригласить эксперта
Ответы на вопрос 3
@Sumor
Если я правильно понимаю, то это просто арифметическая прогрессия на кольце вычетов по модулю M.
Так что нужно рассчитать сумму членов арифметической прогрессии по формуле:
((K + K*N)/2 * N) % M
Ответ написан
Alexandroppolus
@Alexandroppolus
кодир
Мысли вслух.

К наблюдениям ещё можно добавить довольно кэпский поинт K < M, думаю понятно почему.

Если К "маленькое", например меньше корня из N, то у нас тут мало прогрессий и они довольно длинные. Границы прогрессий и "точки приземления" можно искать с шагом не менее sqrt(N) - делаем такой шаг, потом в его окрестности за О(1) отыскиваем границу, - итого сложность не более O(sqrt(N)).

Вот что делать для "больших" К, пока не совсем понятно...
Ответ написан
Комментировать
ALLIGATOR
@ALLIGATOR
def calc(n,k,m):
  l = [i*k%m for i in range(m)]
  return sum(l)*((n+1)//m) + sum(l[:(n+1)%m])
  

print(calc(7, 3, 5))


https://www.online-ide.com/5RpHe9U6kS
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы