洛谷3951 NOIP2017 小凯的疑惑（Day 1 T1）

WWX

https://www.luogu.org/problemnew/show/P3951
题目描述

小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有 无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小 凯想知道在无法准确支付的物品中，最贵的价值是多少金币？注意：输入数据保证存在 小凯无法准确支付的商品。

输入格式：

两个正整数 a 和 b，它们之间用一个空格隔开，表示小凯中金币的面值。

输出格式：

一个正整数 N ，表示不找零的情况下，小凯用手中的金币不能准确支付的最贵的物品的价值。

样例输入：3 7

样例输出：11

WWX

我们再可以利用反证法和整除的知识证明a*b-a-b一定不可以被支付（不是很难，过程就不写了）
所以答案就是a*b-a-b，代码就不贴了。

胡雨菲菲

1. #include <cstdio>
   
2. typedef long long LL;
   
3. int main() {
   
4.     LL a,b,c;
   
5.     scanf("%lld%lld", &a, &b);
   
6.     c = a * b - a - b;
   
7.     printf("%lld", c);
   
8.     return 0;
   
9. }
   

复制代码

WWX

a*b-a-b即是要求的解
我们可以简单的证明一下
证明当k>ab-a-b时，小凯可以准确支付这个物品。
显然，可以列出一个不定方程ma+nb=k，（m n,为未知数）由于m，n是金币个数，所以m>-1,n>-1,
这个不定方程的通解为m=m0+bt，n=n0-at，（仅仅为写法的一种，不过这样写最方便，m0，n0为方程的一组解），
m0+bt>-1,n0-at>-1,化简后有-（m0+1）/b<t<(n0+1)/a,
显然（n0+1)/a-(-(m0+1)/b)=(n0+1)/a+(m0+1)/b=(bn0+b+a+am0)/ab,
又因为bn0+am0=k.所以原式等于（k+a+b）/ab，显然k+a+b>ab,所以原式大于1，所以区间（-（m0+1）/b，(n0+1)/a,）中必有一个整数，t一定存在，所以命题成立。