返回题库

邮票凑数

Stamp Sum

专题
Brainteaser / 脑筋急转弯
难度
L2

题目详情

你有无限多张面值为 5 与 21 的邮票。问:不能表示为这两种邮票线性组合的最大金额是多少?

You possess an infinite supply of stamps valued at 55 and 2121. What is the highest value that cannot be represented as a combination of these stamps?

解析

由于 gcd(5,21)=1\gcd(5,21)=1,不能表示的最大数为 Frobenius 数:

521521=79.5\cdot 21-5-21=79.

因此最大不能凑出的金额是 79。


Original Explanation

The values 2121, 4242, 6363, and 8484 are the smallest numbers equivalent to 11, 22, 33, and 44 modulo 55, respectively. By adding multiples of 55 to these values, we can create any number equivalent to those in modulo 55. The largest value that cannot be formed is the highest number that is 44 modulo 55, which is 7979. Thus, 7979 is the largest integer we cannot create.