【限时免费】20天拿下华为OD笔试之 【模拟】2023B-整数分解【欧弟算法】全网注释最详细分类最全的华为OD真题题解

题目描述与示例

题目描述

一个整数可以由连续的自然数之和来表示。 给定一个整数，计算该整数有几种连续自然数之和的表达式， 并打印出每一种表达式。

输入描述

一个目标整数 t，1 <= t <= 1000

输出描述

1. 该整数的所有表达式和表达式的个数，如果有多种表达式，自然数个数最少的表达式优先输出
2. 每个表达式中按自然数递增输出
3. 具体的格式参见样例
4. 在每个测试数据结束时，输出一行 Result:X
5. 其中 X 是最终的表达式个数

示例一

输入

9
1

输出

9=9
9=4+5
9=2+3+4
Result:3
1
2
3
4

说明

整数 9 有三种表达方法

示例二

输入

10
1

输出

10=10
10=1+2+3+4
Result:2
1
2
3

解题思路

本题一种比较容易想到的做法是对正整数列表[1, 2, 3, ..., n]进行不定滑窗过程，维护窗口和为n即可。下面介绍一种数学解法。

假设某个连续的正整数序列a1, a2, a3, ..., ak的和为n。

正整数序列a1, a2, a3, ..., ak是一个首项为a1，项数为k，公差为1的等差数列。根据等差数列求和公式，存在以下式子成立

n = (a1+ak)*k//2 = (a1+a1+(k-1))*k//2 = a1*k+(k-1)*k//2
1

对于上述式子而言，n是输入的已知量，k和a1均为未知数，因此考虑枚举其中一个未知数来获得另一个未知数的值。

k包含二次项，a1只包含一次项，为了避免使用二次求根公式，我们选择枚举k来获得a1。

上述式子进行变换可得 a1*k = n-(k-1)*k//2

可以确定：项数k的最小值为1，最大值是使得n-(k-1)*k//2 > 0的最大数。由于a1还必须是一个整数，因此我们还需要判断(n-(k-1)*k//2) % k是否为0。若是，则对应的a1存在。

代码

Python

# 题目：2023B-整数分解
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：模拟
# 代码看不懂的地方，请直接在群上提问


n = int(input())
ans = 0
# 初始化k为1
k = 1
# 枚举k，当n-(k-1)*k//2 小于等于0时，不再枚举
while n-(k-1)*k//2 > 0:
    # 若a1是一个正整数，输出一组答案
    if (n-(k-1)*k//2) % k == 0:
        a1 = (n-(k-1)*k//2) // k
        ans += 1
        print(f"{n}={'+'.join(str(a1+i) for i in range(k))}")
    # k递增
    k += 1

print(f"Result:{ans}")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int ans = 0;
        int k = 1;
        
        while (n - (k - 1) * k / 2 > 0) {
            if ((n - (k - 1) * k / 2) % k == 0) {
                int a1 = (n - (k - 1) * k / 2) / k;
                ans++;
                StringBuilder result = new StringBuilder(String.valueOf(n) + "=");
                for (int i = 0; i < k; i++) {
                    result.append(a1 + i);
                    if (i < k - 1) {
                        result.append("+");
                    }
                }
                System.out.println(result);
            }
            k++;
        }
        System.out.println("Result:" + ans);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

C++

#include 

using namespace std;

int main() {
    int n;
    cin >> n;
    int ans = 0;
    int k = 1;
    
    while (n - (k - 1) * k / 2 > 0) {
        if ((n - (k - 1) * k / 2) % k == 0) {
            int a1 = (n - (k - 1) * k / 2) / k;
            ans++;
            cout << n << "=";
            for (int i = 0; i < k; i++) {
                cout << a1 + i;
                if (i < k - 1) {
                    cout << "+";
                }
            }
            cout << endl;
        }
        k++;
    }
    cout << "Result:" << ans << endl;
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

时空复杂度

时间复杂度：O(sqrt(N))。大概需要枚举sqrt(N)次。

空间复杂度：O(1)。仅需若干常数空间。

---

华为OD算法/大厂面试高频题算法练习冲刺训练

• 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！

• 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

• 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

• 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

• 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

• 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

• 绿色聊天软件戳 od1336了解更多