I was trying to solve problem ‘1234 - Harmonic Number’, I wrote the following code
long long H( int n ) { long long res = 0; for( int i = 1; i <= n; i++ ) res = res + n / i; return res; }
Yes, my error was that I was using the integer divisions only. However, you are given n, you have to find H(n) as in my code.
Input Input starts with an integer T (≤ 1000), denoting the number of test cases.
Each case starts with a line containing an integer n (1 ≤ n < 231).
Output For each case, print the case number and H(n) calculated by the code.
Sample Input 11 1 2 3 4 5 6 7 8 9 10 2147483647 Sample Output Case 1: 1 Case 2: 3 Case 3: 5 Case 4: 8 Case 5: 10 Case 6: 14 Case 7: 16 Case 8: 20 Case 9: 23 Case 10: 27 Case 11: 46475828386
数据很大，所以暴力肯定会超时，所以应该试着去找规律（不好找） 规律如下： 对于一个值 n / i 的个数有 n / i - n / ( i +１）个 但是这样暴力的话是O(n),2^32 暴力的话应该也会超，所以还得找找别的地方。于是发现当这个数（n / i）大于 sqrt(n) 时，可以暴力求 n / i,对于小于的用规律求个数再乘以这个数。
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<queue> #include<algorithm> #define ll long long #define inf 0x3f3f3f3f #define maxn 1000007 // 1e6+7 using namespace std; int main() { int t; scanf("%d",&t); ll ans = 0; int n; for(int i = 1 ; i <= t; i ++) { ans = 0; scanf("%d",&n); int tmp = (int)sqrt(n*1.0); for(int j = 1; j <= tmp; j ++) ans += (n/j - n/(j+1)) * j; for(int j = 1; j <= tmp; j ++) ans += n / j; if( n / tmp == tmp) ans -= tmp; printf("Case %d: %lld\n",i,ans); } return 0; }