2024年华为OD机试真题-数的分解

华为OD机试真题-数的分解-2024年OD统一考试（D卷）

题目描述：

给定一个正整数n，如果能够分解为m(m > 1)个连续正整数之和，请输出所有分解中，m最小的分解。

如果给定整数无法分解为连续正整数，则输出字符串"N"。

输入描述：

输入数据为一整数，范围为（1, 2^30]

输出描述：

比如输入为：

21

输出：

21=10+11

补充说明：

21可以分解的连续正整数组合的形式有多种

21=1+2+3+4+5+6

21=6+7+8

21=10+11

输出，21=10+11，是最短的分解序列。

示例1

输入：

21

输出：

21=10+11

说明：

21可以分解的连续正整数组合的形式有多种

21=1+2+3+4+5+6

21=6+7+8

21=10+11

因21=10+11，是最短的分解序列。所以答案是21=10+11

解题思路：

从小开始枚举m即可，从数学公式可知，大概枚举到n的开方值左右即可。 

c++解法：

#include<bits/stdc++.h>
using namespace std;
#define int long long
 
signed main()
{
    int sum; // 用于存储输入的整数n
    cin >> sum; // 读取输入
    bool f = 0; // 标志变量，用来表示是否找到了合适的分解方式
    vector<int> ans; // 用于存储最终的连续整数序列
 
    for (int m = 2; ; m++) // 从最小的可能的m开始循环，直到找到合适的分解或者不可能再分解
    {
        if ((2 * sum) % m != 0) // 如果2*sum不能被m整除，则该m不可能是合适的分解个数
            continue; // 跳过当前循环迭代
 
        int y = 2 * sum / m - m + 1; // 计算可能的序列的第一个数字
        if (y <= 0) break; // 如果第一个数字不大于0，说明找到的m值过大，终止循环
 
        if (y % 2 == 0) // 检查y是否为偶数，这是确保可以从正整数开始的必要条件
        {
            f = 1; // 标记已找到至少一个有效的分解
            for (int x = y / 2; x < y / 2 + m; x++) // 从计算得出的起始数字开始，添加m个连续的整数到ans中
                ans.push_back(x);
            break; // 找到了最小的m，退出循环
        }
    }
 
    if (f) // 如果找到了至少一个有效的分解
    {
        cout << sum << "=" << ans[0]; // 输出sum和序列的第一个数字
        for (int i = 1; i < ans.size(); i++) // 遍历序列，输出剩余的加号和数字
            cout << "+" << ans[i];
        cout << endl; // 输出换行符
    }
    else
        cout << "N" << endl; // 如果没有找到任何有效的分解，输出"N"
    
    return 0;
}