题解 P3951 【小凯的疑惑】

xeri_chen · 2019-08-01 13:56:47 · 题解

看了很多大佬的题解，说实话本人真的太弱了，所以几乎看不懂，于是自己手推了一个解法，也不知道是否有前人发过，如果有什么论证错误或繁琐的地方望各位大佬指出。

首先因为a，b是正整数且互素，易证：a>1 , b>1 , a\ne b

然后显然任何能被支付的数都可以表示为 ma+nb(m\in N ,n\in N)

任何不能被支付的数都可以表示为 ma+nb(m<0\|n<0)

下面开始正文

设答案为k;

k+a必定可以被支付

于是有 k+a=ma+nb(m\in N ,n\in N)

k=(m-1)a+nb

因为k不能被支付所以m-1<0即m<1;

所以m=0;

k=nb-a;

设n=a+x (x\ge-a)

因为b>1，所以b-1>0;

则当且仅当x<0时k不能被支付

当x取最大值-1时k最大

k=（b-1）a-b =ab-a-b;

最后代码就省略了，一个简单的输入输出想必大家都会