How to find ∑1<=i<=n(k mod i) ?

general
1

Given two numbers k and n, we have to find ∑1<=i<=n(k mod i),
Constraints n>=1 n < k<=10^9
time limit- 1s
obvious approach is

r = 0;

for i from 1 to n do

	r += (k mod i);

return r

But it exceeds time limit, Is there a mathematical property to solve this problem in time?

2

can u provide the problem link

3

finding total sum and then taking mod…?
i guess it will work…
try this…

4

@kashish55 mod by what number?

1 Like
5

there exits a sqrt(n) solution, i am formulating that solution, and will post it in a few minutes.

1 Like
6

@darkshadows, eagerly waiting for your O(sqrt(n)) solution :slight_smile:

1 Like
7

Conclusion:
there will be at most O(Sqrt(N)) distinct values for floor(N/i).
Prove:
if i < sqrt(N) there will be at most sqrt(N) values
if i > sqrt(N) there will be at most sqrt(N) values (because floor(N/i) < sqrt(N))

sigma K mod i
= sigma K - floor(K / i) * i
= N * K - sigma floor(K / i) * i

we can calculate sigma floor(K / i) * i fastly for all i that floor(K / i) is the same.

Here is the code

 for (long long i = 1; i <= min(n, k); i++){
    	long long t = k / i, r = min(k / t, n);
    	ans += k * (r - i + 1) - t * (i + r) * (r - i + 1) / 2ll;
    	i = r;
    }
    if (n > k) ans += k * (n - k);
2 Likes