MYOJ_1349:(洛谷P3951)[NOIP 2017 提高组] 小凯的疑惑(数学公式套用，两步搞定代码)

提示

本题代码纯属数学的结晶，因此肥肠简单，但需要一定理解。

题目描述

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

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

输入

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

输出

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

样例输入输出

输入 3 7

输出 11

思路 

很好，现在到了展示公式的时间了。

有请                        Frobenius数

有请                        g(a,b)=ab−a−b

验证：

当a=3，b=7

g(3,7)=3×7−3−7=21−10=11g(3,7)=3×7−3−7=21−10=11(✔)

1.证明(反证法):

假设ab - a - b = ax + by，那么：

ab−a−b=ax+byab−a−b=ax+bya(b−1−x)=b(y+1)a(b−1−x)=b(y+1)

因为a和b互素，所以a必须整除y + 1。设y + 1 = ka，则：

a(b−1−x)=bkaa(b−1−x)=bkab−1−x=bkb−1−x=bkx=b−1−bkx=b−1−bk

因为x ≥ 0，所以：

b−1−bk≥0b−1−bk≥0b−1≥bkb−1≥bkk≤(b−1)/bk≤(b−1)/b

由于b ≥ 2（因为a和b互素且为正整数），(b - 1)/b < 1，而k是非负整数，所以k=0。

如果k=0，那么y + 1 = 0 ⇒ y = -1，这与y ≥ 0矛盾。因此，假设不成立，ab - a - b无法表示为ax + by。

2.证明任何大于ab - a - b的数都可以表示

考虑n > ab - a - b，即n ≥ ab - a - b + 1 = (a - 1)(b - 1)。

由于a和b互素，根据Schur's theorem或Coin Problem的理论，任何足够大的整数都可以表示为ax + by。具体来说，最大的不能表示的数是ab - a - b。

重磅代码

#include<stdio.h>
long long a,b;
int main()
{scanf("%lld%lld",&a,&b);printf("%lld",a*b-a-b);
}

运行结果(这代码竟然被我过了一道洛谷黄题)