题目描述

多整数可以由一段连续的正整数序列（至少两个数）相加而成，比如 25=3+4+5+6+7=12+13。

输入一个整数 N，输出 N 的全部正整数序列，如果没有则输出 NONE。

样例

输入样例：

25

输出样例：

3 4 5 6 7
12 13

题解

1.等差数列求和公式

-> Sn=(a1+an)k/2=(2a+k-1)k/2

设首项和项数，枚举首项a找项数k

#include<cmath>
#include<iostream>
using namespace std;
double a;
int main()
{//Sn=(a1+an)k/2=(2a+k-1)k/2
    double num=0,x;
    cin>>x;
    for(int k=sqrt(x*2);k>1;k--){
        a=(2*x/k+1-k)/2.00;
//        cout<<a<<"-----"<<k<<endl;
        if(a==(int)a)
        {
            num++;
            int ans=a;
            for(int j=k;j>0;j--)
            {
            cout<<ans<<" ";
            ans++;
            }
            cout<<endl;
        }
    }if(!num)
    cout<<"NONE"<<endl;
    return 0;
}

2.二分

-> （首项+末项）×项数/2

设首项和末项，枚举首项i二分末项j

#include <iostream>
#include <algorithm>

using namespace std;
using ll = long long;

int main()
{
    int n;
    cin >> n;
    bool ok = false;
    for(int i = 1; i <= n / 2; i ++ )   // 枚举a1
    {
        // 二分an
        ll l = i + 1, r = n / 2 + 1;
        while(l < r)
        {
            ll mid = l + r + 1 >> 1;
            long long x = (i + mid) * (mid - i + 1) / 2;
            if(x <= n) l = mid;
            else r = mid - 1;
        }
        if((i + r) * (r - i + 1) / 2 == n)//（首项+末项）×项数/2
        {
            for(int j = i; j <= r; j ++ ) printf("%d ", j);
            puts("");
            ok = true;
        }
    }
    if(!ok) puts("NONE");
    return 0;
}

3.质因数

-> 原理2n=k*（a+k-1）

设首项和项数k，寻找2n质因数/整数k求解

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> primes;// 用来存质因数
int n;
int f = 0;
int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n * 2 / i; i ++) // 这里取巧，不全部存起来，只存一对中的小的那个
        if (n * 2 % i == 0)
            primes.push_back(i);
    for (int i = primes.size() - 1; i >= 0; i --) {
        int k = primes[i];
        if ((n * 2 - k * (k - 1)) % (2 * k) != 0) continue; // 判断是否为可行解
        f = 1;//这个是用来判断是否输出 NONE 的
        int x = (n * 2 - k * (k - 1)) / (2 * k);
        for (int j = 1; j <= k; j ++) cout << x ++ << ' ';
        cout << endl;
    }
    if (f == 0) cout << "NONE" << endl;
    return 0;
}

4.求根公式

-> （首项+末项）×项数/2

4.1 设首项i末项j，枚举i求根公式解j

#include<iostream>
#include<cmath>
using namespace std;
int main(){
    long long n;
    cin>>n;
    bool flag=0;
    for(long long i=1;i<=(n+1)/2;i++){
        double j=(sqrt(1+4*(2*n+i*i-i))-1)/2.0;

        if((int)j==j){
            //cout<<j<<" ";
            flag=1;
            for(int k=i;k<=j;k++)cout<<k<<" ";
            cout<<endl;
            //i=j-1;
        }
    }
    if(!flag)cout<<"NONE";
}

4.2 设首项i项数j，枚举首项求项数

#include<iostream>
#include<cmath>
using namespace std;
int main(){
    long long n;
    cin>>n;
    bool flag=0;
    for(long long i=1;i<=(n+1)/2;i++){
        double j=(1-2*i+sqrt(4*(+i*i-i+2*n)+1))/2.0;
        //    cout<<j<<" ";
        if((int)j==j){
            flag=1;
            int ans=i;
            for(int k=j;k>0;k--){
                cout<<ans<<" ";
                ans++;
            }
            cout<<endl;
            //i=j-1;
        }
    }
    if(!flag)cout<<"NONE";
}