2012-05-07 14:35:52Morris
[UVA][Math] 11526 - H(n)
Problem G
H(n)
Input: Standard Input
Output: Standard Output
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
|
事實上, 我用模擬的方式來寫, 不過可以估算的是, 大概是在 Sqrt(N) 左右的時間,
但由於黑心的負數, 我吃了好多怪怪的 WA, 又由於是模擬中間運算多了很多除法,
時間跑得太慢了
//ANSI C 0.632
#include <stdio.h>
#include <math.h>
int main() {
int t, n;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
if(n <= 0) {
puts("0");
continue;
}
long long ans = 0;
int j, k = n, l, r;
for(j = 1; ;) {
r = n/j, l = n/(j+1);
ans += (long long)j*(r-l);
k -= r-l;
if(k == 0) break;
j = n/k;
}
printf("%lld\n", ans);
}
return 0;
}