盯住目标

该代码用于判断一个整数 num 是否可以被拆分成若干个连续整数的和，并输出这些连续整数。

思路检索

若这个数字可以被cnt个连续整数表示, 那 num/cnt 与 cnt*(num/cnt) 相差的值有如下规律:

1. 若为奇数个数的cnt值, 则 num - cnt * (num / cnt) 为k倍cnt

2. 若为偶数个数的cnt值, 则 num - cnt * (num / cnt) + cnt / 2 为k倍cnt

细节处理

1. 计算基准值和偏移

   • 计算基准值 p = num / cnt

   • 计算偏移量 o = num - cnt * p

2. 条件判断

   • 如果 p - (cnt - 1) / 2 < 1，跳过当前 cnt

   • 如果 cnt 为奇数且 o % cnt != 0，跳过当前 cnt

   • 如果 cnt 为偶数且 (o + cnt / 2) % cnt != 0，跳过当前 cnt

3. 输出结果

   • 如果满足条件，计算起始值 low = p - (cnt - 1) / 2

   • 输出从 low 开始的 cnt 个连续整数

备注

若答案段数由少到多, 则循环cnt可以调整为从小到大, 第一个判断条件可以改为break, 在段数无法更多时跳出来减少计算量

时间复杂度 O(n)

C++ 代码

// https://www.acwing.com/problem/content/3720/
#include <iostream>

using namespace std;

int main(){

    bool tag=false; int num; cin >> num;

    for (int cnt = num - 1; cnt > 1; --cnt) {

        int p =  num / cnt, o = num - cnt * p; 

        if ((p - (cnt - 1) / 2) < 1) continue;              
        if ((cnt % 2) && (o % cnt)) continue;               // 奇数个存在判断
        if (!(cnt % 2) && ((o + cnt / 2) % cnt)) continue;  // 偶数个存在判断
        tag = true;

        int low = p - (cnt - 1) / 2;

        for (int i = 0; i < cnt; ++i){
            cout << low + i;
            if (i != cnt - 1) cout << ' ';
        }

        cout << endl;
    }

    if (!tag) cout << "NONE";
}