当前位置 博文首页 > nameofcsdn的博客：幂和、多边形数

最大化 缩小

    nameofcsdn的博客：幂和、多边形数

    作者：[db:作者] 时间：2021-07-11 22:26

    目录

    一，幂和

    二，多边形数

    三，OJ实战

    51Nod - 2172 ProjectEuler 6

    一，幂和

    幂和F_k(n)=\sum _{i=1}^n i^k

    其中最常见的是F_1(n)=\sum _{i=1}^n i=\frac{n(n+1)}{2}，? ?F_2(n)=\sum _{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}

    那么，有没有求取高阶幂和的通用方法呢？

    通用方法有很多，这里介绍高中数学常用的数列技巧的方法：

    x(x+1)(x+2)...(x+k-1)=\frac{x(x+1)...(x+k)-(x-1)x...(x+k-1)}{k+1}

    两边累积求和得到?\sum_{i=1}^ni(i+1)...(i+k-1)=\frac{n(n+1)...(n+k)}{k+1}

    如k=3，\sum_{i=1}^ni(i+1)(i+2)=\frac{n(n+1)(n+2)(n+3)}{4}

    即F_3(n)+3F_2(n)+2F_1(n)=\frac{n(n+1)(n+2)(n+3)}{4}

    所以F_3(n)=\frac{n(n+1)(n+2)(n+3)}{4}-3*\frac{n(n+1)(2n+1)}{6}-2*\frac{n(n+1)}{2}=\frac{n^2(n+1)^2}{4}

    ?

    二，多边形数

    三角形数S_3(n)=\frac{n(n+1)}{2}

    四边形数S_4(n)=n^2

    五边形数S_5(n)=\frac{3n^2-n}{2}

    六边形数S_6(n)=2n^2-n

    一般的，S_k(n)=(k-2)\frac{n(n-1)}{2}+n

    不难发现，S_3(2n-1)=S_6(n)?即六边形数都是三角形数

    ?

    三，OJ实战

    51Nod - 2172 ProjectEuler 6

    ?

    前10个正整数的平方和是
    ?1^2+2^2+?+10^2=385

    前10个正整数和的平方是
    ?(1+2+?+10)^2=3025

    和的平方减去平方和是3025 - 385 = 2640。

    输入n，求前n个正整数和的平方 减去 平方和。

    Input

    输入第一行组数T， 接下来T行，每行一个整数n。 (1 <= T <= 100) (1 <= n <= 300)

    Output

    对于每组数据，输出一个数，表示和的平方减去平方和。

    Sample Input

    3
3
10
100

    Sample Output

    22
2640
25164150
    #include<iostream>
using namespace std;

int main()
{
    long long t,n;
    cin>>t;
    while(t--){
        cin>>n;
        cout<<n*(3*n+2)*(n*n-1)/12<<endl;
    }
    return 0;
}

    ?

    cs
    上一篇：nameofcsdn的博客：lambda表达式入门
    下一篇：没有了