markdown炸了，重发一个：
@[kkksc03](/space/show?uid=1) @[lin\_toto](/space/show?uid=256)
#### 说明
这个做法是我在考场上想出来的 ex\_gcd 做法，当时并没有想到打表，所以向发表一下让大家彻底摆脱小学奥数带来的阴影，我现在仍然认为，ex\_gcd 是这道题的标算。
#### 题解
首先，我们发现这两个数是**互质**的，并且有**无限**个。很容易想到不定方程 $ax + by = gcd(a, b)$ ，其中 $gcd(a, b) = 1$ 。
;然后我们考虑，对于所有可行的能被 $a$ 和 $b$ 表示出来的数 $k$ ，都存在 $x \geq 0, y \geq 0,ax + by = k$。
现在我们要构造的是**最大的不合法的数**，显然，这个数 $+ 1$ 一定是一个合法的数，转化成了求**最大的减一后不合法的数**。
  由于这个数 $k$ 一定是合法的，所以满足性质
$$\exists x \geq 0, \exists y \geq 0,ax + by = k$$
  那么如果 $k-1$ 合法，那么 $k - 1$ 可以表示成
$$a \left ( x - x' \right ) + b \left ( y - y' \right ) = k$$
或
$$a \left ( x - x'' \right ) + b \left ( y - y'' \right ) = k$$
其中 $x',y'$ 表示 $ax + by = 1$ 的 $x$ 最小且非负的整数解，$x'',y''$ 表示 $ax + by = 1$ 的 $y$ 最小且非负的整数解。
那么现在只需要让 $x - x' < 0$ 并且 $y - y'' < 0$ 即可
那么最后的**最大的减一后不合法的数**就是
$$a \left ( x' - 1 \right ) + b \left ( y' - 1 \right ) $$
那么最后的**答案**就是
$$a \left ( x' - 1 \right ) + b \left ( y' - 1 \right ) - 1$$ 。
#### 证明：
首先充分性成立。
然后证明必要性：若$a \left ( x' - 1 \right ) + b \left ( y' - 1 \right ) $不是**最大的减一后不合法的数**，那么一定存在一个更大的数，该数的 $a$ 的系数大于 $x' - 1$ 或 $b$ 的系数大于 $y - 1$ 。显然，减一后仍然是合法的。必要性成立。
#### 代码：
```cpp
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b){
return b == 0 ? a : gcd(b, a % b);
}
void ex_gcd(ll a, ll b, ll &x, ll &y){
if(b == 0){
x = 1, y = 0; return;
}
ex_gcd(b, a % b, y, x);
y -= (a / b) * x;
}
ll a, b;
int main(){
cin >> a >> b;
if(a > b) swap(a, b);
ll x, y;
ex_gcd(a, b, x, y);
if(x > 0){
swap(a, b);
swap(x, y);
}
ll tmp = (-x) / b;
x = x + tmp * b;
y = y - tmp * a;
while(x < 0) x = x + b, y = y - a;
while(x > 0) x = x - b, y = y + a;
ll ans;
ll xx2 = x + b;
ans = a * (xx2 - 1) + b * (y - 1);
cout << ans - 1 << endl;
return 0;
}
```
by infinityedge @ 2017-11-19 17:43:10
%%%楼主
by Gypsophila @ 2017-11-19 19:38:15
@[kkksc03](/space/show?uid=1) @[lin\_toto](/space/show?uid=256)
之前发的又出现了一点偏差，这一版本改正了一些错误
#### 说明
这个做法是我在考场上想出来的 ex\_gcd 做法，当时并没有想到打表，所以向发表一下让大家彻底摆脱小学奥数带来的阴影，我现在仍然认为，ex\_gcd 是这道题的标算。
#### 题解
首先，我们发现这两个数是**互质**的，并且有**无限**个。很容易想到不定方程 $ax + by = gcd(a, b)$ ，其中 $gcd(a, b) = 1$ 。
然后我们考虑，对于所有可行的能被 $a$ 和 $b$ 表示出来的数 $k$ ，都存在 $x \geq 0, y \geq 0,ax + by = k$。
现在我们要构造的是**最大的不合法的数**，显然，这个数 $+ 1$ 一定是一个合法的数，转化成了求**最大的减一后不合法的数**。
由于这个数 $k$ 一定是合法的，所以满足性质
$$\exists x \geq 0, \exists y \geq 0,ax + by = k$$
那么如果 $k-1$ 合法，那么 $k - 1$ 可以表示成
$$a \left ( x - x' \right ) + b \left ( y - y' \right ) = k$$
或
$$a \left ( x - x'' \right ) + b \left ( y - y'' \right ) = k$$
其中 $x',y'$ 表示 $ax + by = 1$ 的 $x$ 最小且非负的整数解; $x'',y''$ 表示 $ax + by = 1$ 的 $y$ 最小且非负的整数解。
那么现在只需要让 $x - x'< 0$ 并且 $y - y'' < 0$ 即可
那么最后的**最大的减一后不合法的数**就是
$$a \left ( x' - 1 \right ) + b \left ( y'' - 1 \right ) $$
那么最后的**答案**就是
$$a \left ( x' - 1 \right ) + b \left ( y'' - 1 \right ) - 1$$
#### 证明：
首先充分性成立。
然后证明必要性：若$a \left ( x' - 1 \right ) + b \left ( y'' - 1 \right ) $不是**最大的减一后不合法的数**，那么一定存在一个更大的数，显然该数的 $a$ 的系数大于 $x' - 1$ 或 $b$ 的系数大于 $y'' - 1$ （如果都小于等于，那么该数不会比当前数大）。显然，减一后仍然是合法的。所以必要性成立。
综上， $a \left ( x' - 1 \right ) + b \left ( y'' - 1 \right ) - 1$ 是最大的不合法的数。
#### 代码：
```cpp
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b){
return b == 0 ? a : gcd(b, a % b);
}
void ex_gcd(ll a, ll b, ll &x, ll &y){
if(b == 0){
x = 1, y = 0; return;
}
ex_gcd(b, a % b, y, x);
y -= (a / b) * x;
}
ll a, b;
int main(){
cin >> a >> b;
if(a > b) swap(a, b);
ll x, y;
ex_gcd(a, b, x, y);
if(x > 0){
swap(a, b);
swap(x, y);
}
ll tmp = (-x) / b;
x = x + tmp * b;
y = y - tmp * a;
while(x < 0) x = x + b, y = y - a;
while(x > 0) x = x - b, y = y + a;
ll ans;
ll xx2 = x + b;
ans = a * (xx2 - 1) + b * (y - 1);
cout << ans - 1 << endl;
return 0;
}
```
by infinityedge @ 2017-11-19 20:10:13
%楼主
by 桑园之鸽 @ 2017-11-19 20:14:15
楼主可以自己发啊
by iodwad @ 2017-11-19 20:27:09
@[ZCDHJ](/space/show?uid=24878)
题解被锁了
by infinityedge @ 2017-11-19 20:32:24
@[infinityedge](/space/show?uid=19241) 眼瞎了...sorry orz顺便请问一下“显然，这个数 + 1 一定是一个合法的数”是为什么
by iodwad @ 2017-11-19 20:40:03
@[infinityedge](/space/show?uid=19241) 好的，加上去咯
by kkksc03 @ 2017-11-19 21:44:04
@[infinityedge](/space/show?uid=19241)
by iodwad @ 2017-11-20 00:45:38
我看到了一篇P9999 ab-a-b的题解
by Jianyang @ 2018-06-26 22:09:56