能访问各种网站的浏览器,手机网站建设价格表,嘉兴网络项目建站公司,网站建设公司工资标准打卡记录 包子凑数#xff08;裴蜀定理 DP#xff09;
根据裴蜀定理#xff0c;存在 c gcd(a, b) 使不定方程ax by c满足条件#xff0c;如果gcd(a, b) 1即a与b互素的情况下#xff0c;就会 ax by 1#xff0c;由于为1可以构造后面的无穷数字#xff0c;故得到结…打卡记录 包子凑数裴蜀定理 DP
根据裴蜀定理存在 c gcd(a, b) 使不定方程ax by c满足条件如果gcd(a, b) 1即a与b互素的情况下就会 ax by 1由于为1可以构造后面的无穷数字故得到结论当 gcd(a, b) 1 时才存在有限无法构造的数字情况。根据定理a b最大无法构造的数字为 (a - 1)(b - 1) - 1而后再采用 0-1 背包的算法思想解决。
import math
import sysn, m int(input()), 10000
nums [int(input()) for _ in range(n)]g nums[0]
for num in nums:g math.gcd(g, num)
if g ! 1:print(INF)sys.exit(0)f [0 for _ in range(m)]for i in range(n):f[nums[i]] 1for j in range(nums[i] 1, m):f[j] | f[j - nums[i]]cnt 0
for i in range(1, m):if f[i] 0:cnt 1print(cnt)
