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

# | User | Rating |
---|---|---|

1 | tourist | 3697 |

2 | Benq | 3583 |

3 | Petr | 3522 |

4 | ecnerwala | 3467 |

5 | Radewoosh | 3466 |

6 | maroonrk | 3369 |

7 | Um_nik | 3358 |

8 | jiangly | 3330 |

9 | Miracle03 | 3314 |

10 | scott_wu | 3313 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 213 |

2 | Errichto | 189 |

3 | awoo | 188 |

4 | rng_58 | 187 |

5 | SecondThread | 186 |

6 | Um_nik | 179 |

7 | Ashishgup | 177 |

8 | maroonrk | 172 |

8 | vovuh | 172 |

8 | antontrygubO_o | 172 |

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

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/15/2021 18:14:39 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

click

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

Then may be Dirichlet's Formula, Though I don't understand it properly. So, can't explain more.

Well, I did google this and I can't come up with a O(sqrt(n)) solution or less

In case you haven't figured out yet

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?

thanks, I coded it and it worked, turns out it's not that hard ....

Can you tell me why "every divisor from (floor(n, d+1)+1, floor(n, d)) can appear d times" please. Thanks :)

We can see that the sum is equivalent to

It's easy to see that

has only O(sqrt(N)) distinct values, so we can group together ranges that has the same division value and use A.P sum.

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$$$.

In total, we have at most $$$2 \cdot \sqrt{n} = O(\sqrt{n})$$$ distinct values.

thanks for helping me out :D

which algo is this ? Can i know ?

Common sense.

We can't run this in O(n). The value of n 1e12

If you have solved it can you please share the soln! Thanks