今天个人赛的一个题
We define the function f(x) = the number of divisors of x. Given two integers a and b (a ≤ b), please
calculate f(a) + f(a+1) + ... + f(b).
Input
Two integers a and b for each test case, 1 ≤ a ≤ b ≤ 231 1.
The input is terminated by a line with a = b
= 0.
Output
The value of f(a) + f(a+1) + ... + f(b).
Sample Input
9 12
1 2147483647
0 0
Sample Output
15
46475828386
Hint
For the first test case:
9 has 3 divisors: 1, 3, 9.
10 has 4 divisors: 1, 2, 5, 10.
11 has 2 divisors: 1, 11.
12 has 6 divisors: 1, 2, 3, 4, 6, 12.
So the answer is 3 + 4 + 2 + 6 = 15.
O(n)的算法很好想
1到m中可以被i整除的数的个数为 m/i
所以用for(sum =0,i=0;i<=m;i++)
sum += m/i;
sum即是f(1)+f(2)+f(m)的值.
这样的算法复杂度是O(N);
但诸位大哥也看到了 数据范围很大 所以我们按照惯例---要优化···
其实我们可以只算从1到sqrt(m) 具体说来每次不但要加m/i 还要加(m/i-m/(i+1))*i;
后面加的那个对应的是跟i对应的另一半···
形象一点吧
拿12来说
就是 12 6 4 3 2 2 1 1 1 1 1 1
我们算的从1到3 后面对应的就是
(12/1-12/2)*1
(12/2-12/3)*2
(12/3-12/4)*3
这个也算规律吧
这样一来规模就是O(sqrt(N))
还是贴CODE：
#include<iostream>
#include <cmath>
using namespace std;
int a[10]={0,1,3,5,8,10};
long long int f(long long int m)
{
if(m<=5) return a[m];
long long int sum=0;
long long int t=sqrt(m*1.0);
for(long long int i=1;i<=t;i++)
{
sum+=m/i;
sum+=(m/i-m/(i+1))*i;
}
return sum;
}
int main()
{
long long int m,n;
while(cin>>m>>n&&(m||n))
cout<<f(n)-f(m-1)<<endl;
}