How to quickly find the remainder of the sum of digits?

Question

C++ / C#

Hello!
The program is given a number (perhaps a very large one), you need to sum all the numbers up to this number and find the remainder of the division of the number, which is also fed to the program. If you give a large number as the first parameter, then the program runs for a very long time. This process needs to be optimized. How can I do that?
Thanks in advance!

Answer 1

If you give a large number as the first parameter, then the program runs for a very long time.

And if instead of summing numbers, use the formula for the sum of an arithmetic progression n * (n + 1) / 2?
How big is a "big number"?

Answer 2

(1+2+...+n)%k = (n*(n+1)/2)%k
= ((n/2)%k * (n+1)%k)%k, for even n
= (n%k * ((n+1)/2)%k)%k, for odd n