首页 > 代码库 > HDU 5053 the Sum of Cube(简单数论)

HDU 5053 the Sum of Cube(简单数论)

http://acm.hdu.edu.cn/showproblem.php?pid=5053

题目大意:

  求出A^3+(A+1)^3+(A+2)^3+...+B^3和是多少

解题思路:

  设f(n)=1~n的立方和,则A^3+(A+1)^3+(A+2)^3+...+B^3=f(B) - f(A - 1)

  题目给的数的范围是1~10000,1~10000立方和不会超过__int64(long long)的范围。由于是10000个数立方和。

所以可以选择打表(不知道立方和的公式,可以选择打表)。

 

立方和公式:1^3+2^3+3^3+4^3+...+n^3 = (n*(n+1)/2)^2

 

AC代码:

这里是是打表的思路

 1 #include<stdio.h> 2 #include<string.h> 3  4 typedef long long LL; 5  6 const LL MAXN = 10001; 7  8 int main(){ 9     int T, A, B;10     LL ans, a[MAXN];11 12     memset(a, 0, sizeof(a));13     for(LL i = 1; i < MAXN; ++i){14         a[i] = a[i - 1] + i * i * i;15     }16 17     scanf("%d", &T);18     for(int cs = 1; cs <= T; ++cs){19         scanf("%d%d", &A, &B);20 21         printf("Case #%d: %I64d\n", cs, a[B] - a[A - 1]);22     }23     return 0;24 }

利用公式:

 1 #include<stdio.h> 2 #include<string.h> 3  4 typedef long long LL; 5  6 LL f(LL n){ 7     return n * (n + 1) * n * (n + 1) / 4; 8 } 9 10 int main(){11     int T, A, B;12     scanf("%d", &T);13     for(int cs = 1; cs <= T; ++cs){14         scanf("%d%d", &A, &B);15         printf("Case #%d: %I64d\n", cs, f(B) - f(A - 1));16     }17     return 0;18 }

 

 

 

 

HDU 5053 the Sum of Cube(简单数论)