转载自 http://blog.csdn.net/synapse7/article/details/12873437
这道题我自己做的时候没有想到好的优化方法，提交的时候借鉴这篇文章的内容，转载如下：
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
11526 - H(n)
Time limit: 5.000 seconds
What is the value this simple C++ function will return?
long long H(int n){
long long res = 0;
for( int i = 1; i <= n; i=i+1 ){
res = (res + n/i);
}
return res;
}
Input
The first line of input is an integer T ( T <= 1000 ) that indicates the number of test cases. Each of the next T line will contain a single signed 32 bit integer n.
Output
For each test case, output will be a single line containing H(n).
Sample Input Output for Sample Input
|
2 5 10 |
10 27 |
怎么计算sum{ [n/i] }？(1<=i<=n)(n<=2147483647)
n太大，硬算肯定不行，我们先观察一个例子，看能否得出一些结论。
当n=20时，和式展开为
20+10+6+5+4+3+2+2+2+2+1+1+1+1+1+1+1+1+1+1
注意到后面相同的数太多，不妨化简下：
20+10+6+5+1*(20-10)+2*(10-6)+3*(6-5)+4*(5-4)
=(20+10+6+5)+(20+10+6+5)-4*4
=2(20+10+6+5)-4*4
也许，我们可以
这样，复杂度就从O(n)降为O(√n)了。