蓝桥杯2025国赛-免费披萨

2026-03-19 暂无评论

全文共 146 字，阅读约 1 分钟

蓝桥杯2025国赛-免费披萨

方法一：

枚举 1～8 的全排列，再枚举 9 个插入位置，插入一个 1～8 的数字。

import os
import sys

# 请在此输入您的代码
ans = []

from math import gcd

n = int(input())

def dfs(num_set: set, path: list):
    if len(path) == 8:
        ans.append(int(''.join(map(str, path.copy()))))
    for i in range(1, 9):
        if i not in num_set:
            num_set.add(i)
            path.append(i)
            dfs(num_set, path)
            num_set.remove(i)
            path.pop()
for i in range(1, 9):
    dfs({i}, [i])

res = 0
best_num = 0

for x in ans:
    num_list = list(str(x))
    # 枚举插入位置
    for i in range(9):
        # 枚举数字
        for j in range(1, 9):
            cur = num_list.copy()
            cur.insert(i, str(j))
            cur_num = int(''.join(cur))
            g = gcd(n, cur_num)
            if g > res:
                res = g
                best_num = cur_num
            elif g == res:
                if cur_num < best_num:
                    best_num = cur_num
print(best_num)

方法二：

使用库函数进行优化

import os
import sys
from math import gcd
from itertools import permutations

# 请在此输入您的代码
n = int(input())

res = 0
best_num = 0

# 直接用 permutations 生成所有排列
for perm in permutations(range(1, 9)):
    # 将排列转为字符串，避免反复 list(str(x))
    base = ''.join(map(str, perm))
    
    # 枚举插入位置和插入数字
    for pos in range(9):
        for d in range(1, 9):
            # 直接构造字符串，不用列表操作
            cur = base[:pos] + str(d) + base[pos:]
            cur_num = int(cur)
            g = gcd(n, cur_num)
            if g > res:
                res = g
                best_num = cur_num
            elif g == res and cur_num < best_num:
                best_num = cur_num

print(best_num)