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

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;

}

巴特西

HDU 2114 Calculate S(n)

最新文章

热门文章