Как быстро найти остаток от суммы цифр?

Question

[timkin1]

Здравствуйте!

Программе подается число (возможно очень большое), нужно просуммировать все числа до этого числа и найти остаток от деления от числа, которое также подается программе. Если первым параметром дать большое число, то программа выполняется очень долго. Необходимо оптимизировать данный процесс. Как это можно сделать?
Заранее спасибо!

Comments

[jcmvbkbc]

необходимо оптимизировать данный процесс. Как это можно сделать?

Зависит от того, какой остаток, каких цифр и для чего оптимизировать.

[timkin1]

jcmvbkbc, остаток от деления, оптимизировать по скорости

[jcmvbkbc]

timkin1, соберись с мыслями и напиши свой вопрос так, чтобы второкласснику было понятно, что нужно сделать и в чём проблема.
Потому что сейчас напрашивается ответ: "суммируй цифры, бери остаток от деления, этот процесс уже оптимален".

[timkin1]

jcmvbkbc, программе подается число (возможно очень большое), нужно просуммировать все числа до этого числа и найти остаток от деления от числа, которое также подается программе. Если первым параметром дать большое число, то программа выполняется очень долго. Из мыслей заменить % на бинарные операции

[Developer]

timkin1, блин, какая программа выполняется очень долго? В условии её нет.

[Roman]

timkin1, просуммировать https://ru.wikihow.com/сложить-целые-числа-от-1-до-N
O(1) это долго?
деление с остатком https://ru.wikipedia.org/wiki/Деление_с_остатком

[Максим Мосейчук]

Я конечно придерживаюсь мнения, что не всем разработчикам нужна математика. Но блядь, не до такой же степени!

Answer 1

[jcmvbkbc]

Если первым параметром дать большое число, то программа выполняется очень долго.

А если вместо суммирования чисел воспользоваться формулой суммы арифметической прогрессии n * (n + 1) / 2 ?
Насколько велико "большое число"?

Comments

[Adamos]

Ну тут вообще не Гаусс пишет вопрос, понятно уже ;)

Answer 2

[Rsa97]

(1+2+...+n)%k = (n*(n+1)/2)%k
= ((n/2)%k * (n+1)%k)%k, для чётных n
= (n%k * ((n+1)/2)%k)%k, для нечётных n