NOIP2017 D1T1 小凯的疑惑

洛谷P3951

$看到题目，很容易想到这一题是求使ax+by=c(a,b,c\inN)无非负整数解的最大c$

$由裴蜀定理可知方程一定有整数解（a,b互素,gcd(a,b)=1|c）$

$解法一：暴力枚举$

$看到题目我的第一想法是求出ax+by=1的解然后枚举c使x,y扩大c倍后仍无非负整数解$

$枚举c应该要从1到a*b\dots\dots看看数据范围就知道会WA掉4个点$

$这个解法很傻瓜我就不再赘述了\dots\dots代码略$

$期望得分：60$

$解法二：小学奥数$

$虽然我不想承认但真**是小学奥数！！$

$因为a,b,c都>0，所以方程的解最多有一个负数$

$不妨设y<0,则x\geq0$

$那么对于c=ax+by，y=-1时c取最大值，c=ax-b$

接下来我们来看x

事实上0≤x≤b-1

为什么呢？

首先注意到这样一个事实：线性方程ax+by=c的整数解可以表示为{x-kb,y+ka}(k∈Z)

因为当x≤b-1时，一定不存在k∈Z使得x-kb≥0且y+ka≥0

这样可能看着不是很清楚，那么我们再反证一下会更容易明白

当x≥b时，显然x-b≥0且y+a≥0（此时k=1），与假设矛盾，故不成立

这样我们就证明了0≤x小于等于号怎么≤b-1

上面我们得出c=ax-b

那么当x=b-1时c取最大值a(b-1)-b=ab-a-b

综上，当y=-1,x=b-1时c取最大值ab-a-b

有的人可能会说，上面假设的是y<0，那x<0的时候c最大值还是不是ab-a-b呢？

很简单，同理，将x=-1,y=a-1代入，c=-a+b(a-1)=ab-a-b

期望得分：100

AC代码（有必要吗……）：

1 #include<cstdio>
2 int main()
3 {
4     long long a,b;//a,b足够大时a*b会爆int 
5     scanf("%lld%lld",&a,&b);
6     printf("%lld",a*b-a-b);
7     return 0;
8 }