I encountered a problem on the web about competitive programming
Problem statement: Given 3 numbers n , a , b $ (n, a , b \le 10^{12}) $. Find the result of the following equation $$ \sum_{i=a}^b n \ mod \ i $$
Example : $ n = 15, a = 1, b = 5$, the answer is 15 % 1 + 15 % 2 + ... + 15 % 5 = 4
The naive solution got time limit exceeded because the constrain is large. I will be pleased if anyone comes up with a more optimal solution
Thanks much for help!
There is no simple formula in general, but (depending on the sizes of the parameters) there may be a shortcut. Note that if $ki \le n < (k+1) i$, $n \; \text{mod}\; i = n - k i$. Thus if $k b \le n < (k+1) a$, $$ \sum_{i=a}^b n\; \text{mod}\; i = \sum_{i=a}^b (n - k i) = (b+1-a)\left(n-\frac{k(a+b)}2\right)$$ Or if $n/a - n/b$ is not too large, you can break up the interval $[a,b]$ into pieces for different $k = \lfloor n/i \rfloor$.