今天個(gè)人賽的一個(gè)題
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整除的數(shù)的個(gè)數(shù)為 m/i
?所以用for(sum =0,i=0;i<=m;i++)
sum += m/i;
?sum即是f(1)+f(2)+f(m)的值.
這樣的算法復(fù)雜度是O(N);
但諸位大哥也看到了 數(shù)據(jù)范圍很大 所以我們按照慣例---要優(yōu)化···
其實(shí)我們可以只算從1到sqrt(m)? 具體說來每次不但要加m/i 還要加(m/i-m/(i+1))*i;
后面加的那個(gè)對應(yīng)的是跟i對應(yīng)的另一半···
形象一點(diǎn)吧
拿12來說
就是 12 6 4 3 2 2 1 1 1 1 1 1
我們算的從1到3 后面對應(yīng)的就是
(12/1-12/2)*1
(12/2-12/3)*2
(12/3-12/4)*3
這個(gè)也算規(guī)律吧
這樣一來規(guī)模就是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;
}