Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link ×

vinhntndu's blog

By vinhntndu, history, 5 weeks ago, In English,

I have a difficulty problem. Let F [n] be the number of positive integer divisors of the integer n. for example F [4] = 3 because 4 has 3 divisors which is {1,2,4}. Give two positive integers a and b (a <b; 1<=a<b<10^12). Calculate F[a] + F[a+1] + ... + F[b]. INPUT 2 5 OUTPUT 9 PLEASE HELP ME. THANK YOU SO MUCH

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

5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by vinhntndu (previous revision, new revision, compare).

5 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

Let $$$S[n]$$$ be $$$F[1]+F[2]+..+F[n]$$$. Notice that $$$F[a]+F[a+1]+..+F[b]=S[b]-S[a-1]$$$ Now the problem is reduced to computing $$$F[n]$$$. Notice that for a fixed number $$$x$$$ divisors come in pairs (denote them $$$d$$$ and $$$x/d$$$, $$$d<=x/d$$$) Notice that $$$d<=sqrt(x)$$$ thus if $$$x<=n$$$, $$$d<=sqrt(n)$$$. You can fix all numbers $$$d<=sqrt(n)$$$ and you can count how many numbers $$$x<=n$$$ for which also $$$d<=x/d$$$ holds to not count twice. This is just something like $$$2*(n/d-d)+1$$$. $$$(n/d)$$$ is how many numbers divide $$$d$$$, excluding the ones for which $$$x/d<=d$$$, multiplied by 2 to also count $$$x/d$$$ and finally adding 1 to count $$$d$$$ as a divisor of $$$d*d$$$ once. Finally, you have an $$$O(sqrt(b))$$$ solution.