首页 > ACM题库 > HDU-杭电 > hdu 2114 Calculate S(n)-数学-[解题报告]C++
2013
12-29

hdu 2114 Calculate S(n)-数学-[解题报告]C++

Calculate S(n)

问题描述 :

Calculate S(n).

S(n)=13+23 +33 +……+n3 .

输入:

Each line will contain one integer N(1 < n < 1000000000). Process to end of file.

输出:

Each line will contain one integer N(1 < n < 1000000000). Process to end of file.

样例输入:

1
2

样例输出:

0001
0009

题目:http://acm.hdu.edu.cn/showproblem.php?pid=2114

 

主要是计算前n项和的公式。

前n项和的立方公式为   : s(n)=(n*(n+1)/2)^2;

 

前n项和的平方公式为:s(n)=n*(n+1)(2*n+1)/6;

 

转自百度搜索:

公式证明  迭代法:

   我们知道:

  0次方和的求和公式ΣN^0=N 即1^0+2^0+…+n^0=n

  1次方和的求和公式ΣN^1=N(N+1)/2 即1^1+2^1+…+n^1=n(n+1)/2

  2次方和的求和公式ΣN^2=N(N+1)(2N+1)/6 即1^2+2^2+…+n^2=n(n+1)(2n+1)/6——平方和公式,此公式可由同种方法得出,取公式(x+1)^3-x^3=3x^2+3x+1,迭代即得。

  取公式:(X+1)^4-X^4=4*X^3+6*X^2+4*X+1

  系数可由杨辉三角形来确定

  那么就得出:

  (N+1)^4-N^4=4N^3+6N^2+4N+1………………………………(1)

  N^4-(N-1)^4=4(N-1)^3+6(N-1)^2+4(N-1)+1…………………..(2)

  (N-1)^4-(N-2)^4=4(N-2)^3+6(N-2)^2+4(N-2)+1………………(3)

  ……………….

  2^4-1^4=4×1^3+6×1^2+4×1+1……………………………..(n)

  .

  于是(1)+(2)+(3)+……..+(n)有

  左边=(N+1)^4-1

  右边=4(1^3+2^3+3^3+……+N^3)+6(1^2+2^2+3^2+……+N^2)+4(1+2+3+……+N)+N

  所以呢

  把以上这已经证得的三个公式代入

  4(1^3+2^3+3^3+……+N^3)+6(1^2+2^2+3^2+……+N^2)+4(1+2+3+……+N)+N=(N+1)^4-1

  得4(1^3+2^3+3^3+……+N^3)+N(N+1)(2N+1)+2N(N+1)+N=N^4+4N^3+6N^2+4N

  移项后得 1^3+2^3+3^3+……+N^3=1/4 (N^4+4N^3+6N^2+4N-N-2N^2-2N-2N^3-3N^2-N)

  等号右侧合并同类项后得 1^3+2^3+3^3+……+N^3=1/4 (N^4+2N^3+N^2)

  即

  1^3+2^3+3^3+……+N^3= 1/4 [N(N+1)]^2

  大功告成!

  立方和公式推导完毕

  1^3+2^3+3^3+……+N^3= 1/4 [N(N+1)]^2

 

 

下面是AC代码:

#include<iostream>
using namespace std;
int main()
{
	__int64 n;
	while(scanf("%dI64d",&n)!=EOF)
	{
		__int64 ans=((n*(n+1)/2)%10000)*((n*(n+1)/2)%10000)%10000;
		printf("%04I64d\n",ans);


	}
	return 0;

}

 

 

解题转自:http://blog.csdn.net/w00w12l/article/details/7007063


  1. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  2. 样例输出和程序输出不吻合,修改一下样例输出吧。我用的是VC编译器,会提示我的i和j变量重复定义

  3. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks