HDU 2114 Calculate S(n)

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

Problem Description

Calculate S(n).

S(n)=1³+2³ +3³ +......+n³ .

 

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
", a[ n % 10000]);
    }
    return 0;
}