题目解析

1. 理解题目的意思

先写一个暴力的代码

import math
from itertools import combinations

def solve_brute_force(N, M):
    count = 0
    print(f"正在寻找 N={N} 中 LCM >= {M} 的方案...\n")
    print(f"{'方案':<10} {'子集':<20} {'LCM值'}")
    print("-" * 40)

    # 1. 枚举子集长度 (从选1个 到 选N个)
    for length in range(1, N + 1):
        # 2. 生成该长度的所有组合
        for subset in combinations(range(1, N + 1), length):
            # 3. 计算该子集的 LCM (Python 3.9+ 支持 *解包传参)
            lcm_val = math.lcm(*subset)
            
            # 4. 判断是否满足条件
            if lcm_val >= M:
                count += 1
                print(f"#{count:<9} {str(subset):<20} {lcm_val}")

    print("-" * 40)
    print(f"最终结果: 共 {count} 种方案")

# 运行题目样例 N=5, M=5
solve_brute_force(5, 5)

运行的结果

方案         子集                   LCM值
----------------------------------------
#1         (5,)                 5
#2         (1, 5)               5
#3         (2, 3)               6
#4         (2, 5)               10
#5         (3, 4)               12
#6         (3, 5)               15
#7         (4, 5)               20
#8         (1, 2, 3)            6
#9         (1, 2, 5)            10
#10        (1, 3, 4)            12
#11        (1, 3, 5)            15
#12        (1, 4, 5)            20
#13        (2, 3, 4)            12
#14        (2, 3, 5)            30
#15        (2, 4, 5)            20
#16        (3, 4, 5)            60
#17        (1, 2, 3, 4)         12
#18        (1, 2, 3, 5)         30
#19        (1, 2, 4, 5)         20
#20        (1, 3, 4, 5)         60
#21        (2, 3, 4, 5)         60
#22        (1, 2, 3, 4, 5)      60
----------------------------------------
最终结果: 共 22 种方案

知道了题目的意思: 集合的数量, lcm(子集) >= M 的数量

代码

正在寻找 N=5 中 LCM >= 5 的方案…