日志5

Chranos是个数学天才。 一天，有一个可爱的小女孩追求Chranos，他知道Chranos最喜欢当且仅当总质量为K克的时候的番茄炒蛋了。她希望通过美食俘获Chranos的胃，这样就一定可以和他在一起了吧！虽然小女孩有无限数量的食材，但是数学王国的番茄和蛋非常特殊，他们的质量分别为N克和M克。为了表现一颗完整的心、表达充足的爱意，所有的食材必须被用完。N和M都是正整数且互素，制作过程中既不会凭空增加质量，也不会凭空消失质量。 Chranos不希望小女孩打扰他学数学。他发现，并不是所有番茄炒蛋都是可以被制作出来的。他想找出最大的不可以被制作出的总质量K来拒绝小女孩，这样Chranos就可以永远和数学在一起了！

这是一个典型的鸡兔同笼问题的变形。由于番茄和蛋的质量是互素的，也就是说，N 和 M 的最大公约数是 1，因此可以应用裴蜀定理来分析。裴蜀定理告诉我们，当且仅当两个数互素时，任意一个不超过某个值的质量都可以通过组合这两个重量得到。

题解思路

根据数学定理，如果有两个互素的正整数 NNN 和 MMM，那么它们组合无法得到的最大质量为：K=N×M−N−M这就是著名的 Frobenius number（弗罗本纽斯数）。

解题步骤

1. 检查番茄和蛋的质量 NNN 和 MMM 是否互素。根据题意，N 和 M 已经互素，因此可以直接跳到第 2 步。
2. 计算 K 值：K=N×M−N−M。

示例

假设番茄的质量为 3 克，蛋的质量为 5 克，那么：K=3×5−3−5=15−3−5=7因此，小女孩无法通过使用 3 克和 5 克的番茄和蛋制作出 7 克质量的番茄炒蛋。