×

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

 1 2 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? asked 02 Jul '13, 13:14 4★v_akshay 1.2k●9●16●25 accept rate: 13% can u provide the problem link (02 Jul '13, 15:32) finding total sum and then taking mod..? i guess it will work.. try this.. (02 Jul '13, 19:50) 1 @kashish55 mod by what number? (02 Jul '13, 20:52) 1 there exits a sqrt(n) solution, i am formulating that solution, and will post it in a few minutes. (02 Jul '13, 21:26) 1 @darkshadows, eagerly waiting for your O(sqrt(n)) solution :) (04 Jul '13, 01:59) v_akshay4★

 2 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);  answered 04 Jul '13, 07:30 6★qdkac 31●2 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×690

question asked: 02 Jul '13, 13:14

question was seen: 3,937 times

last updated: 04 Jul '13, 07:31