Too many divisors - A possible New Problem

Thanks for the problem and for notification! These careful hints make quite an intrigue :)

Problem #354 is now online!

Surprisingly I soon caught the glimpse of the idea and hint about O(sqrt(N)) was influential in recognizing the idea as correct, but still it required perhaps couple hours efforts of my poor brain to carefully shape it out... Anyway it feels much simpler after one picks the idea, moreover after it is solved. Thanks for that exercise :)

Well, I would be curious to know the "thought process" employed by colleagues in solving this, but as they haven't yet left any comments, I suspect that for tough guys like Mathias and Vladimir (and the new unknown hero under the name "tzyLee") the idea seemed less or more obvious, unlike in my case :)

Is the O(sqrt N) approach meant to be by getting the sum of the number of all divisors, or just getting the number of divisors for a given number?

Because I've found an O(sqrt N) algorithm for the number of divisors, but I can't figure out how to get the sum of number of divisors for the entire range in O(sqrt N) time, only in roughly O(N sqrt N)

There's probably a trick I'm missing somewhere because the checker can't possibly take as long as the solutions I'm doing, but I'm stumped, and I just wanted to double check that there is a better algorithm for the whole range.

(I'm trying to be as vague as I possibly can, given that this is an open thread.)

Sometimes, the problem asks you "can you compute the grand total for quantity X in range R?", and the immediate reaction could be, "sure, I'll just compute this quantity for every number in R and then get the total".

In this cases, it could be useful to stand back and notice that the problem isn't asking you to actually compute this quantity for every number in the range - only the total for all numbers.

And sometimes, the latter could be quicker.