http://acm.hdu.edu.cn/showproblem.php?pid=2114
Problem Description
Calculate S(n).
S(n)=13+23 +33 +......+n3 .
Input
Each line will contain one integer N(1 < n < 1000000000). Process to end of file.
Output
For each case, output the last four dights of S(N) in one line.
Sample Input
1
2
Sample Output
0001
0009
时间复杂度：$O(n)$
代码：
#include <bits/stdc++.h>
using namespace std; long long a[10010]; long long A(long long x) {
return x * x % 10000 * x % 10000;
} int main() {
long long n, S;
for(int i = 1; i <= 10000; i ++) {
a[i] = (a[i-1] + A(i))%10000;
}
while(~scanf("%lld", &n)) {
printf("%04lld\n", a[ n % 10000]);
}
return 0;
}