题解 | #尼科彻斯定理#

HJ76尼科彻斯定理

一.题目描述

给出一个数m，利用m个连续的奇数求和的结果是m的立方，输出m个数。

例如：
1^3=1
2^3=3+5
3^3=7+9+11
4^3=13+15+17+19

二.算法一(暴力)

首先我们知道输出m个数是连续的并且全是小于m的立方的，我们可以采用暴力枚举的方法求出其和(对于其连续的m个奇数我们可以采用求和公式)，下面是完整的代码：

#include<bits/stdc++.h>
using namespace std;
int num;
int main(){
    while(cin>>num){
        int ans=num*num*num;
        for(int i=3;i<=ans;i++){
            if(i%2==0) continue;
            int sum=0;
            //等差数列求和 st表示等差数列的首项 ed表示其末项
            int st=i,ed=2*num+(st-2);
            //首项加末相乘以项数除以二
            sum=(st+ed)*num/2;
            if(sum==ans){
                //求和结果是立方和
                for(int k=i;k<i+num;k++){
                    //输出每一项
                    if(k==i+num-1){
                        cout<<st+(k-i)*2<<endl;
                    } else {
                        cout<<st+(k-i)*2<<"+";
                    }
                }
            }
        }
    }
    return 0;
}

时间复杂度：$O(n^3)O(n^\{3\})$，因为是要求其的和等于立方，所以从3开始直接遍历到其立方，所以复杂度是$O(n^3)O(n^\{3\})$。

空间复杂度：$O(1)O(1)$，不需要什么额外空间。

三.算法二(数学)

很显然这道题目有着浓浓的数学味道，下面是完整的数学推导(博主字丑，勿怪)，下面是完整的代码：

#include<bits/stdc++.h>
using namespace std;
int num;
int main(){
    while(cin>>num){
        int st=num*num-num+1;//st表示开始的第一项
        for(int i=1;i<=num;i++){
            //对num项进行输出
            if(i!=1){
                cout<<"+"<<st+(i-1)*2;
            } else {
                cout<<st;
            }
        }
        cout<<endl;
    }
    return 0;
}

时间复杂度：$O(n)O(n)$，只需要用for循环输出最后的奇数序列。

空间复杂度：$O(1)O(1)$，不需要什么额外空间。