【NOIP2017】小凯的疑惑

本题在洛谷上的链接：https://www.luogu.org/problemnew/show/P3951#sub

这是去年复赛第一题，小凯的疑惑？我的疑惑？我的疑惑就是为什么我去年初赛挂了？！后天就是今年的初赛了，希望能过。。。（哭）

关于这道题的各种吐槽不再多说，有兴趣可以自行去看看其他地方。这里正儿八经解决一下小凯的疑惑。

 实际上这是道小学奥数题，答案是ab-a-b，怎么想出来的，我是不知道，但可以验证这是对的。而且我看到有个地方称这是赛瓦维斯特定理（已知a，b为大于1的正整数，gcd(a,b)=1，则使不定方程ax+by=c无负整数解的最大整数c=a*b-a-b）。

接下来进入证明环节。首先要证明ab-a-b不可以被pa+qb所表示，我们利用反证法，假设ab-a-b=pa+qb。

则有ab=(p+1)a+(q+1)b，因为gcd(a,b)=1，那么a|(p+1)，b|(q+1)，不妨设p+1=k₁a，q+1=k₂b，可以得出k₁+k₂=1。而k₁a=p+1>=1，所以k₁>=1，同理k₂>=1，推出矛盾，所以假设不成立，ab-a-b不可以表示成pa+qb。

接下来要证明对于任意c>=ab-a-b，c都可以表示pa+qb的形式。

显然，有c>=ab-a-b+1，c+a+b>=ab+1，不妨设c+a+b=ka+m，k>=b，1<=m<=a-1，若m等于a其实就相当于k=b+1。

暂时转化一下视角，我们来考虑ax+by=m这个不定方程，因为gcd(a,b)=1，所以一定有解。根据二元一次不定方程的性质，若存在一个特解x0，那么x₀+kb/gcd(a,b)也一定是解。

所以一定存在b-1<=x₁<=-1使得方程成立，因为x₁的取值是连续的b-1个。因为ax₁<0，b>0，m>0，所以y₁>=1。

取x=k+x1-1，y=y1-1，可知x>=0，y>=0。此时ax+by=kx+ax₁-a+y₁b-b，因为ax₁+by₁=m，那么ax+by=kx+m-a-b，我们发现他刚好等于c。因此得出结论对于任意c>=ab-a-b，一定可以表示成ax+by的形式（当然x>0且y>0）。

这道题难在理解答案而不在正确通过。

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 typedef long long ll;
 6 
 7 int main() {
 8     ll a, b;
 9     cin >> a >> b;
10     cout << a * b - a - b;
11     return 0;
12 }

AC代码

【NOIP2017】小凯的疑惑

原文：https://www.cnblogs.com/Mr94Kevin/p/9774214.html