华师一附中OI组

标题: 洛谷3951 NOIP2017 小凯的疑惑（Day 1 T1） [打印本页]
作者: WWX    时间: 2018-6-5 17:31
标题: 洛谷3951 NOIP2017 小凯的疑惑（Day 1 T1）
本帖最后由 WWX 于 2018-6-5 17:34 编辑

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

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

输出格式：

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

样例输入：3 7
样例输出：11





作者: WWX    时间: 2018-6-5 17:38
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一定存在，所以命题成立。
作者: 胡雨菲菲    时间: 2018-6-5 17:39
  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    时间: 2018-6-5 17:41
我们再可以利用反证法和整除的知识证明a*b-a-b一定不可以被支付（不是很难，过程就不写了）
所以答案就是a*b-a-b，代码就不贴了。



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2