横沥仿做网站,网站后台更新后主页不显示,徐州网站建设系统,wordpress 架构题意#xff1a;让我们求f#xff08;n#xff09;n/1n/2n/3......n/n#xff1b;同时注意n/i取整#xff1b;
思路#xff1a;首先我们先看数据的范围#xff0c;n (1 ≤ n 2 31)#xff0c;数据范围太大#xff0c;如果我们按 照题目中的代码直接暴力肯定超时…题意让我们求fnn/1n/2n/3......n/n同时注意n/i取整
思路首先我们先看数据的范围n (1 ≤ n 2 31)数据范围太大如果我们按 照题目中的代码直接暴力肯定超时那么我们就要优化代码
fn/x这个函数关于y x 对称对称点刚好是sqrt(n)于是就简单了直接 求sumn/i (i*in i 1)然后乘以2再减去i*i即可。
例如当n10时msqrt(10)13f(10)1053*2-3*327
关于m对称左右相差m*m左边105318右边22111119和左边相差3*39
故这道题我们就可以简化了
公式1.msqrtn 2. fnn/1n/2n/3......n/k*2-m*mn/km;
题目
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 |。 /| 。 /| 。 /| 。 /| 。 /| * 。 /
sqrt(n)|———————————/。| * / | 。| * / *| 。| / | 。| / * |* 。
_______|_/_________|______________。___sqrt(n)
由图可知可将题转化为求每个整数坐标点对应的矩形面积,由图形对称可知求到sqrt(n),*2即可
因多加了一次边长为sqrt(n)正方形的面积故减去即可
代码
#includestdio.h
#includemath.h
int main()
{int t,k1;scanf(%d,t);while(t--){long long n,sum0;scanf(%lld,n);int m(int)sqrt(n);for(int i1; im; i)sumsumn/i;sum*2;sum-m*m;printf(Case %d: %lld\n,k,sum);}return 0;
}
