题解 P3951 【小凯的疑惑】

· · 题解

首先，作为D1T1，这道题一定很简单啦。我指的是代码。所以不要想得太复杂啦。考场上我爆零了。在这道题AC的那一瞬间，呈现在我眼前的是那熟悉而陌生的梦想（A+B problem）。

对于扩欧的做法我就不提了，反正考场上我也想不到。这道题的最简做法那就是找规律。

所以在大量（两三个）数据的对比中会发现当答案 N=（a-1）b-a也就是ab-a-b时为最大解。这个答案为何可靠呢？

a,b互质，设k为正整数，

则（a-k）*b与a也是互质的,

所以（a-k）*b-a不等于ax+by(x,y为正整数).

所以当k取1时(a-k)*b-a取最大值。

对于a同理可得(b-1)*a-b。

然后我们会惊喜的发现两次答案都指向同一个数

                 ——a*b-a-b.

废话不多说，上AC小宝贝儿：

#include<cstdio>
using namespace std;
long long a,b;
int main(){
    scanf("%lld%lld",&a,&b);
    printf("%lld",(a-1)*b-a);
    return 0;
}

这真是一篇上完竞赛第一课的小朋友都看得懂的代码啊。