NOIP2017 小凯的疑惑 解题报告(赛瓦维斯特定理)

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

题解：

我只想说。。。我考试的时候没有想到这茬, 

$a*b-a-b$ 

于是17年NOIP水的不成样子

其实，这道题目是一道数学定理——赛瓦维斯特定理：已知a,b为大于1的正整数，(a,b)=1,则使不定方程$ax+by=C$无负整数解的最大整数$C=ab-a-b$ ！

证明：

若存在$x,y>=0$满足 $ax+by=ab-a-b$ 则$a(x+1)+b(y+1)=ab$

于是$a|(y+1)$,$b|(x+1)$

($a(x+1)=b(a-y-1)$，有 a,b互质，所以$b|(x+1)$。$a|(y+1)$同理）

又$x+1>=1,y+1>=1$

故$a(x+1)+b(y+1)>=a*b+b*a=2ab$ (因为$b|(x+1)$,所以$b<=x+1$,同理$a<=y+1$)

但是在上述假设中我们知道$a(x+1)+b(y+1)=ab$,$a>=0,b>=0$

所以假设不成立，即不存在$x,y>=0$,满足 $ax+by=ab-a-b$

 

对于任意正整数$C>=ab-a-b+1$， 即$C+a+b>=ab+1$

设$C+a+b=ka+m(k>=b,1<=m<=a-1)$

注意到(a,b)=1

由裴蜀定理，知存在$x_0,y_0∈Z$，使得 $ax_0+by_0=1$

故存在$x_1,y_1∈Z，-(b-1)<=x_1<=-1$

使得$ax_1+by_1=m$

(解释一下，这里的意思其实是设$-(b-1)<=x_1<=-1$，一定存在整数$y_1$使得$ax_1+by_1=m$成立。原因就是在整数$x_1$的取值中一共有$b-1$个数，$y_1=(m-ax_1)/b$，总是可以找到$x_1$使得$m-ax_1$能被b整除）

显然，$y_1>=1(ax_1<0,m>0,b>0$，因此$y_1>=1$)

于是，取$x=k+x_1-1,y=y_1-1$

注意到$x_1,y_1$的取值范围，得$x,y>=0$

得$ax+by=C$

所以任意$C>=ab-a-b+1$都存在$x,y>=0$,$ax+by=C$

证毕