You are not logged in. Please login at www.codechef.com to post your questions!

×

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

v_akshay's gravatar image

4★v_akshay
1.2k91625
accept rate: 13%

can u provide the problem link

(02 Jul '13, 15:32) rahul_nexus2★

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

(02 Jul '13, 19:50) kashish554★
1

@kashish55 mod by what number?

(02 Jul '13, 20:52) betlista ♦♦3★
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) darkshadows ♦5★
1

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

(04 Jul '13, 01:59) v_akshay4★

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);
link

answered 04 Jul '13, 07:30

qdkac's gravatar image

6★qdkac
312
accept rate: 0%

edited 04 Jul '13, 07:31

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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