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

Question

[Wataru]

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

Мои наблюдения:
Можно найти 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 шаг длинее остальных. Вроде тут напрашивается какая-то рекурсия, но я не смог это формализовать.

Comments

[mayton2019]

Можно попробовать распечатать значения каждого слагаемого табличкой и там будут характерные ... хм.. периоды чтоли.

[Anton F]

Предположение.
Выглядит, что есть ряд (0, K*1, K*2, ..., K*N) и от каждого из членов этого ряда берется остаток деления на М.
Если K*N < M, то кроме линейной вроде не получится.
Если больше, то можно узнать период (возможно его не будет), когда остаток будет повторяться, например, это произойдет на элементе 0 < n < N, тогда в остатке ряда (K*(n+1), K*N), можно посчитать количество вхождений этих n элементов p, домножить полученную на предыдущем этапе сумму на число вхождений, и добавить остатки для оставшегося ряда (K*(p*n + 1), K*N).
Сложность такого алгоритма будет быстрее, чем О(N) (предположу, примерно, O(N/M), но все же линейным.

[Anton F]

Anton F, а точнее, в худшем случае все равно линейным, в лучшем O(N/M)

[Wataru]

Anton F, Период и так известен. Это M (если сократить k и m на gcd, как указано в вопросе). Именно эта идея с отбрасыванием полных периодов уже расписана в вопросе (абзац "Дальше, можно считать, что N < M...") И сложность остается O(N % M), что ничем не лучше, если N < M.

Answer 1

[Sumor]

Если я правильно понимаю, то это просто арифметическая прогрессия на кольце вычетов по модулю M.
Так что нужно рассчитать сумму членов арифметической прогрессии по формуле:
((K + K*N)/2 * N) % M

Comments

[Wataru]

Очень интересная идея, но, к сожалению, не работающая. Вот если бы в конце еще был %M добавлен- то да. Но нет. Модуль берется от каждого слагаемого. Иначе я скобки расставил в вопросе.

Контрпример: N=2, K=3, M=7:

0%7+3%7+6%7 = 0+3+6 = 9

Ваша формула может дать только меньше остатка, т.е. до 6. А ответ 9.

Да, действительно, так можно найти остаток от ответа по модулю M. Но это мало что дает.

Answer 2

[Alexandroppolus]

Мысли вслух.

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

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

Вот что делать для "больших" К, пока не совсем понятно...

Answer 3

[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

Comments

[Wataru]

И какая же, по вашему, сложность у этого алгоритма?

[ALLIGATOR]

Wataru, O(M)

[ALLIGATOR]

прошу прощения, вы этот вариант в вопросе тоже разобрали, если M>>N, то сложность относительная тоже высокая

[Wataru]

Все-равно, спасибо за ответ!