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

vinhntndu's blog

By vinhntndu, history, 5 weeks ago, ,

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

• -5

 » 5 weeks ago, # |   0 Auto comment: topic has been updated by vinhntndu (previous revision, new revision, compare).
 » 5 weeks ago, # |   +14
 » 5 weeks ago, # |   +21 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.
•  » » 5 weeks ago, # ^ |   0 thank you