《怎样解题:数学竞赛攻关宝典(第3版)》第 36 页:
题2.2.19 湾区快餐店出售炸鸡块,并将这些鸡块打包出售, 一包中包含 7 块或 11 块鸡块。 求最大正整数 n, 使得你无论鸡块包怎么组合都不能恰好得到 n 块炸鸡块。 你能将此推广吗?
此题等价于:令 x 和 y 是非负整数,z = 7x + 11y 不能表达的最大正整数是多少?我们有:
- 7·(-3) + 11·2 = 1
- 7·8 + 11·(-5) = 1
第一个等式是利用扩展欧几里得算法在线计算器计算出来的。第二个等式是利用:
- 7x + 11y = 7(x+11) + 11(y-7)
因此:
易知,本题的答案是 59。
本题的一种推广是假设一包中包含 a 块或 b 块鸡块,其中 a 和 b 互素。
例如,假设 a = 5, b = 21,则:
- 5·(-4) + 21·1 = 1
- 5·17 + 21·(-4) = 1
因此:
易知答案是 79。
例如,假设 a = 105, b = 2048,则:
- 105·(-39) + 2048·2 = 1
- 105·2009 + 2048·(-103) = 1
因此:
易知答案是 212887。
根据小学徒的评论,从 The Frobenius Coin Problem Upper Bounds on The Frobenius Number 可知,有以下定理:
给定大于 1 的互素的整数 a 和 b,令 x 和 y 是非负整数,则 ax + by 不能表达的最大正整数是 ab - a - b。
Luckytoilet的答案列在这
https://github.com/luckytoilet/projecteuler-solutions/blob/master/Solutions.md
1 2 3 4 5 6 8 9 10 12 13 15 16 17 19 20 23 24 26 27 30 31 34 37 38 41 45 48 52 59
1 2 3 4 6 7 8 9 11 12 13 14 16 17 18 19 22 23 24 27 28 29 32 33 34 37 38 39 43 44 48 49 53 54 58 59 64 69 74 79