SP11560 PUCMM210 - A Summatory

我的blog

题目链接：SP11560 PUCMM210 - A Summatory

\[description\]

输入T和T个n

求出
\[ \sum_{i=1}^{n}\sum_{j=1}^{i}j^3 \]

\[solution\]

结论：

对于任意一个
\[f(n)=\sum_{i=1}^{n}i^3\ \ \ (n\in N^* ) \]
满足
\[f(n)=\frac{n^2(n+1)^2}{4}\]

### 证明：
当\(n=1\)时，
\[\sum_{i=1}^ni^3=1^3=\frac {1^2\times2^2}{4}\]
显然成立

设当\(k=n\)时成立
则 \(\sum_{i=1}^ki^3=\frac{k^2(k+1)^2}{4}\)成立
此时
\[1^3+2^3+...+k^3=\frac{k^2(k+1)^2}{4}\]
\[1^3+2^3+...+k^3+(k+1)^3=\frac{k^2(k+1)^2}{4}+(k+1)^3\]
\[1^3+2^3+...+k^3+(k+1)^3=\frac{k^2(k+1)^2+4(k+1)^3}{4}\]
\[1^3+2^3+...+k^3+(k+1)^3=\frac{(k^2+4k+4)(k+1)^2}{4}\]
\[1^3+2^3+...+k^3+(k+1)^3=\frac{ (k+2)^2 (k+1)^2}{4}\]
所以此时\(k+1=n\)成立

所以
\[f(n)=\sum_{i=1}^{n}i^3=\frac{n^2(n+1)^2}{4}\ \ \ (n\in N^* ) \]

\[code\]

#include <cstdio>
#define re register
using namespace std;
template<typename T>
inline void read(T&x)
{
    x=0;
    char s=(char)getchar();
    bool flag=false;
    while(!(s>='0'&&s<='9'))
    {
        if(s=='-')
            flag=true;
        s=(char)getchar();
    }
    while(s>='0'&&s<='9')
    {
        x=(x<<1)+(x<<3)+s-'0';
        s=(char)getchar();
    }
    if(flag)
        x=(~x)+1;
}
int T,n;
const int N=1e6,mod=1000000003;
int f[N+5];
int main()
{
    for(re int i=1; i<=N; ++i)
        f[i]=(int)((f[i-1]+1ll*i*i%mod*(i+1)%mod*(i+1)%mod*250000001%mod)%mod);//250000001是4关于1000000003的逆元 
    read(T);
    while(T--)
    {
        read(n);
        printf("%d\n",f[n]);
    }
    return 0;
}

SP11560 PUCMM210 - A Summatory

原文：https://www.cnblogs.com/wangjunrui/p/12241910.html