1226. 包子凑数
摘要
Title: 1226. 包子凑数
Tag: 完全背包
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1226. 包子凑数
-
题意
给出n个数，问有多少个数是这n个数凑不出来的
-
思路
完全背包问题
- 如果这n个数的，说明由他们凑出来的数一定是的倍数，所以肯定有无穷个凑不出来
- 如果这n个数的，根据裴蜀定理，最大不能表示出来的数必定有个上界，因为两个数a,b（当gcd=1时），最大不能表示出来的 数是：a*b - (a + b)，当数字更多的时候，这个上界必然更小（可选的数字变多了），而99和98是100内最大的互质的数，所以这个上界选择，也就是体积最大选
剩下的就按照完全背包做即可
-
代码
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
30
31
32
33
34
35'''
Author: NEFU AB-IN
Date: 2022-04-04 20:08:15
FilePath: \ACM\Acwing\1226.py
LastEditTime: 2022-04-04 20:08:21
'''
def gcd(a, b):
return gcd(b, a % b) if b else a
N = int(1e4 + 10)
n = int(input())
a, f = [], [0] * N
d = 0
for i in range(n):
x = int(input())
a.append(x)
d = gcd(d, x)
if d > 1:
print("INF")
exit(0)
f[0] = 1
for i in range(n):
for j in range(a[i], N):
f[j] = f[j] | f[j - a[i]]
ans = 0
for i in range(N):
if not f[i]:
ans += 1
print(ans)