NKOJ9669小凯的疑惑—证明

小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。

现在小凯想知道：

1.在无法准确支付的物品中，最贵的价值是多少金币？

2.共有多少种无法支付的物品？

注意：输入数据保证存在小凯无法准确支付的商品。

第一问

设 $ax + by = d$ , 化简可得 $y = -\dfrac{a}{b}x + \dfrac{d}{d}$

将其带入平面直角坐标系中。

那么答案显然为一个不在第一象限，与坐标轴上的点。

我们不妨取 $x = -1, y = a - 1$，此时 $d$ 必不能被形如 $ax + by = d$ 的方式所表示。

代入解得 $d = ab - a - b$。

证毕。

第二问

不难发现，第二问本质上就是在第一问的基础上找一个点$A$在第二象限，点$B$在第四象限的点。

所以对于点 $A$ 便有 $(a - 1)$ 种方案。

同理，对于点 $B$ 便有 $(b - 1)$ 方案。

易证得总方案数为$\dfrac{(a - 1)(b - 1)}{2}$。

即 $\dfrac {1}{2} \times (ab - a - b)$。

证毕。