数的分解 - 华为OD统一考试（C卷）

OD统一考试（C卷）

分值： 100分

题解： Java / Python / C++

alt

题目描述

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

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

输入描述

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

输出描述

比如输入为:

输出:

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 的问题。

代码的主要逻辑是枚举可能的分解个数 m，并计算对应的起始值 s，检查是否能够满足条件。

如果找到满足条件的分解，返回最小的分解。

Java

import java.util.Scanner;
/**
 * @author code5bug
 */
public class Main {

    // 找到最小的正整数个数，使得连续正整数之和等于给定整数 n
    static String solve(int n) {
        // 从小到大枚举分解个数 m，如发现可行的分解则返回结果
        for (int m = 2; m < n; m++) {
            // 连续正整数之和 > n，退出循环
            if ((1 + m) * m / 2 > n) {
                break;
            }

            // 假设以 s 开始 m 个连续正整数之和为 n
            // 计算 s 的值，即 (2 * n / m - m + 1) / 2 的值
            int s = ((2 * n / m - m + 1) / 2);

            // n 可以分解成 m 个连续正整数
            if ((2 * s + m - 1) * m / 2 == n) {
                StringBuilder result = new StringBuilder();
                result.append(n).append('=');
                for (int i = s; i < s + m; i++) {
                    result.append(i);
                    if (i < s + m - 1) {
                        result.append('+');
                    }
                }
                return result.toString();
            }
        }

        return "N";
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.println(solve(n));
    }
}

Python

import math


def solve(n):
    for m in range(2, n):  # 从小到大枚举分解个数 m ，如发现可行的分解则返回结果
        if (1 + m) * m / 2 > n:  # 连续正整数之和 > n ，退出循环
            break

        # 假设以 s 开始 m 个连续正整数之和为 n， 则有 (s + (s + m - 1)) * m / 2 = n
        # 计算 s 的值，即 (2 * n / m - m + 1) / 2 的值
        s = int((2 * n / m - m + 1) / 2)
        if (2 * s + m - 1) * m / 2 == n:  # n 可以分解成 m 个为连续正整数
            return f"{n}={'+'.join(str(i) for i in range(s, s + m))}"

    return "N"


if __name__ == "__main__":
    n = int(input())
    print(solve(n))

C++

#include <iostream>

using namespace std;

// 找到最小的正整数个数，使得连续正整数之和等于给定整数 n
string solve(int n) {
    // 从小到大枚举分解个数 m，如发现可行的分解则返回结果
    for (int m = 2; m < n; m++) {
        // 连续正整数之和 > n，退出循环
        if ((1 + m) * m / 2 > n) {
            break;
        }

        // 假设以 s 开始 m 个连续正整数之和为 n
        // 计算 s 的值，即 (2 * n / m - m + 1) / 2 的值
        int s = ((2 * n / m - m + 1) / 2);

        // n 可以分解成 m 个连续正整数
        if ((2 * s + m - 1) * m / 2 == n) {
            string result;
            result += to_string(n) + '=';
            for (int i = s; i < s + m; i++) {
                result += to_string(i);
                if (i < s + m - 1) {
                    result += '+';
                }
            }
            return result;
        }
    }

    return "N";
}

int main() {
    int n;
    cin >> n;
    cout << solve(n) << endl;

    return 0;
}

🙏整理题解不易，如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏

#面经##华为##春招##秋招##校招#