首页 > 代码库 > 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(简单数论)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。