i_am_eating_wa_and_tle's blog

Help needed on a number theory problem.
By i_am_eating_wa_and_tle, history, 7 years ago, In English

problem link: http://lightoj.com/volume_showproblem.php?problem=1098

PDF Link: lightoj.com/volume_showproblem.php?problem=1098&language=english&type=pdf

I think this problems solution is Summation of ((floor(N/i) — 1) * i) .But n is 10^9. It will definately get TLE if I precalculate or use loop.I think there exist something that I do not know yet.Please help me solve this problem. If I need to learn any theory/algorithm to solve this problem please mention it.

Thank you very much.

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
7 years ago, # |
  Vote: I like it +43 Vote: I do not like it

There's one remark about floor (N/i) is that for i = 1 to N there will only be O(sqrt(N)) value of floor(N/i) so you can loop through all the value of floor(N/i) then calculate the range of the value then sum them together.

→ Reply