Можно ли быстрее чем за 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 шаг длинее остальных. Вроде тут напрашивается какая-то рекурсия, но я не смог это формализовать.
Предположение.
Выглядит, что есть ряд (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, а точнее, в худшем случае все равно линейным, в лучшем O(N/M)
Написано
Wataru
@wataru Автор вопроса, куратор тега Математика
Anton F, Период и так известен. Это M (если сократить k и m на gcd, как указано в вопросе). Именно эта идея с отбрасыванием полных периодов уже расписана в вопросе (абзац "Дальше, можно считать, что N < M...") И сложность остается O(N % M), что ничем не лучше, если N < M.
Если я правильно понимаю, то это просто арифметическая прогрессия на кольце вычетов по модулю M.
Так что нужно рассчитать сумму членов арифметической прогрессии по формуле:
((K + K*N)/2 * N) % M
Wataru
@wataru Автор вопроса, куратор тега Математика
Очень интересная идея, но, к сожалению, не работающая. Вот если бы в конце еще был %M добавлен- то да. Но нет. Модуль берется от каждого слагаемого. Иначе я скобки расставил в вопросе.
Контрпример: N=2, K=3, M=7:
0%7+3%7+6%7 = 0+3+6 = 9
Ваша формула может дать только меньше остатка, т.е. до 6. А ответ 9.
Да, действительно, так можно найти остаток от ответа по модулю M. Но это мало что дает.
К наблюдениям ещё можно добавить довольно кэпский поинт K < M, думаю понятно почему.
Если К "маленькое", например меньше корня из N, то у нас тут мало прогрессий и они довольно длинные. Границы прогрессий и "точки приземления" можно искать с шагом не менее sqrt(N) - делаем такой шаг, потом в его окрестности за О(1) отыскиваем границу, - итого сложность не более O(sqrt(N)).
Вот что делать для "больших" К, пока не совсем понятно...