### 514977059's blog

By 514977059, history, 15 months ago,

Hi, I'm stuck on this problem, but I'm unable to find a solution which I could understand. Can someone explain it to me

• +1

 » 15 months ago, # |   +3
•  » » 15 months ago, # ^ |   0 uh sorry, but the problem tells us to compute the sum of sum of divisors of i for i = 1 -> n, not the sum of divisors of n only
•  » » » 15 months ago, # ^ | ← Rev. 3 →   0 Then may be Dirichlet's Formula, Though I don't understand it properly. So, can't explain more.
•  » » » » 15 months ago, # ^ |   0 Well, I did google this and I can't come up with a O(sqrt(n)) solution or less
•  » » » » » 15 months ago, # ^ |   0
 » 15 months ago, # |   +7 For a divisor d, d can appear floor(n, d) times as divisor of all number 1-n. E.g. n=100, d=2 then 2 can appear 50 times as divisor We also know that every divisor from (floor(n, d+1)+1, floor(n, d)) can appear d times. E.g. n=100, d=2 then every divisor from (34, 50) can appear 2 times.Can you see O(sqrt(n)) approach from this?
•  » » 15 months ago, # ^ |   0 thanks, I coded it and it worked, turns out it's not that hard ....
•  » » 12 months ago, # ^ |   0 Can you tell me why "every divisor from (floor(n, d+1)+1, floor(n, d)) can appear d times" please. Thanks :)
 » 15 months ago, # | ← Rev. 2 →   +10 We can see that the sum is equivalent to $\sum_{i} \lfloor\dfrac{n}{i}\rfloor * i$It's easy to see that $\lfloor\dfrac{n}{i}\rfloor$has only O(sqrt(N)) distinct values, so we can group together ranges that has the same division value and use A.P sum.
•  » » 15 months ago, # ^ | ← Rev. 2 →   +1 In case you're wondering why the sum has only $O(\sqrt{n})$ distinct values:There are 2 cases for $\left \lfloor{\frac{n}{i}}\right \rfloor$. $i \leq \sqrt{n}$. There are only $\sqrt{n}$ such values. $i > \sqrt{n}$. In this case, $\left \lfloor{\frac{n}{i}}\right \rfloor < \sqrt{n}$, so there are at most $\sqrt{n}$ distinct values. In total, we have at most $2 \cdot \sqrt{n} = O(\sqrt{n})$ distinct values.
•  » » » 15 months ago, # ^ |   0 thanks for helping me out :D
 » 10 months ago, # |   0 """ Well there is a simple O(n) method to do this problem. It is shown in the below python code. n = int(input()); ans = 0; for i in range(1, n+1): ans += i * (n // i); print(ans); But we need to solve this problem in O(sqrt N) to pass the test cases. So this is kinda hack. For the first half of the (sqrt N) values we will use different technique, and use O(n) solution for the rest remaining half. """ M = 10**9+7 ## AP Summation Formulae; def summation(l, r): n = r - l + 1 return n * ( l + r) // 2; ## First Part; n = int(input()); ans = 0; i = 1; minVal = n while( i*i <= n): l = n // (i + 1); r = n // i if(l >= r): continue ans+= i * (summation(l + 1, r)) minVal = l ans %= M; i += 1; ## Second Part; for i in range(1, minVal + 1): ans += i * (n // i) ans %= M; print(ans % M);
•  » » 6 months ago, # ^ |   -6 which algo is this ? Can i know ?
•  » » » 6 months ago, # ^ |   +6 Common sense.
•  » » 6 weeks ago, # ^ |   0 We can't run this in O(n). The value of n 1e12
 » 2 months ago, # |   0 If you have solved it can you please share the soln! Thanks