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\n", ans(n));
}
return 0;
}
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索c++
， int
， function
， long
， 数论
category
uva11572、11518 uva、h.zhang uva.nl、http 218.26.115.219、218.26.115..219，以便于您获取更多的相关知识。