给定一个自然数 N,0≤ N ≤ 4999和 M 各不同的十进制数字 X1,X2,……,XM, 找出由这些数字所构成的正整数中 N 的倍数最小的正整数,设该正整数不超过 2 32-1。 输入要求: 输入的第一行有两个整数,分别为该自然数 N 和数字的个数 M,第 2 行有 M 个数字( 0≤ M ≤ 9),数字之间用空格隔开。 输出要求: 输出一行为由这些数字所组成的该自然数的最小倍数,数字可重复使用。如果不存在这样的数,则输出 0.
时间: 2024-03-07 17:48:04 浏览: 242
这是一道比较经典的数学问题,可以用数论和搜索算法来解决。下面是一种可能的算法:
1. 首先将输入的数字从小到大排序,这样可以保证搜索到的第一个符合要求的数一定是最小的。
2. 定义一个状态,表示当前已经组成的数,初始状态为 0。
3. 从小到大依次遍历输入的数字,对于每个数字,有两种选择:选或不选。如果选择了该数字,就将它加到当前状态中,并检查是否能够整除 N,如果能,则返回当前状态;如果不能,则继续搜索。如果不选该数字,则直接跳过。
4. 如果遍历完所有数字,仍然没有找到符合要求的数,则返回 0。
下面是一个 Python 代码的实现,时间复杂度为 O(2^M),其中 M 是数字的个数,空间复杂度为 O(M)。
```python
def gcd(a, b):
# 计算 a 和 b 的最大公约数
if b == 0:
return a
else:
return gcd(b, a % b)
def lcm(a, b):
# 计算 a 和 b 的最小公倍数
return a * b // gcd(a, b)
def dfs(nums, n, state):
# nums: 输入的数字列表
# n: 目标倍数
# state: 当前状态,表示已经组成的数
if state > 0 and state % n == 0:
# 如果当前状态整除 n,则返回该状态
return state
for i in range(len(nums)):
# 依次选择每个数字
next_state = state * 10 + nums[i]
result = dfs(nums, n, next_state)
if result > 0:
return result
# 如果所有数字都不行,则返回 0
return 0
n, m = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort()
result = dfs(nums, n, 0)
if result == 0:
print(0)
else:
print(result)
```
需要注意的是,这个算法的时间复杂度非常高,如果输入的数字个数很多,可能需要优化算法,比如使用动态规划或者数学方法来计算最小倍数。
阅读全文