首页 / 软件开发 / 数据结构与算法 / UVa 11526 H（n） （数论）

UVa 11526 H（n） （数论）2014-10-02 csdn博客 synapse7

11526 - H（n）

Time limit: 5.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2521

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

也许，我们可以

本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45351.htm

这样，复杂度就从O（n）降为O（√n）了。

完整代码：

/*0.206s*/#include<cstdio>#include<cmath>typedef long long ll;inline ll ans（ll n）{ll r = 0, m = sqrt（n）, i;for （i = 1; i <= m; ++i） r += n / i;return （r << 1） - m * m;}int main（）{int t;ll n;scanf（"%d", &t）;while （t--）{scanf（"%lld", &n）;printf（"%lld
", ans（n））;}return 0;}