好久不见，开学和假期天天搞csp实在没时间搞CSDN,终于抽出一点时间来写会文章了。
我们先来看一道NOIP提高组的题目
题目描述
小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中，最贵的价值是多少金币？
注意：输入数据保证存在小凯无法准确支付的商品。
输入格式
两个正整数 a 和 b，它们之间用一个空格隔开，表示小凯中金币的面值。
输出格式
一个正整数 N，表示不找零的情况下，小凯用手中的金币不能准确支付的最贵的物品的价值。
输入输出样例
输入 #1
3 7
输出 #1
11
【数据范围与约定】
对于 30% 的数据： 1≤a,b≤50。
对于 60%的数据： 1≤a,b≤10^4
对于100%的数据：1≤a,b≤10^9
10^9次方的数据范围，大家是不是觉得很难，那我们先看一下代码。
#include <iostream>
#include <string>
using namespace std;
long long a, b;
int main() {
cin >> a >> b;
cout << a * b - a - b;
return 0;
}这就AC代码啦，实际就两行，那这是怎么推出来的呢？我们先做几组样例
样例1：4 7 样例2：2 3 样例2: 5 7
我们先硬算一下
第一组 16，第二组 1，第三组23
相信有的同学已经看出来就是两数之积减两数之和，这就是在数论四大定理中的裴蜀定理基础上证明出来的。
裴蜀定理：ax+by=gcd(a,b) 该等式一定有整数解
为什么呢？
我们用更相减损证明一下
更相减损：a,b的d(最大公约数)=b,a-b的最大公约数
那b,a-b的d也等于a-b,b-(a-b)的d吗？那最后不就是我们要的x,y的解吗？
更相减损的一直减，也可与简化为辗转相除，我们来看一下简化过程。
（余的数学形式：a-a/b(整除)*b)
bx'-(a-a/b*b)y' = d (因为x,y会变，所以是x',y')
那x',y'倒退回x,y的方程只需要提取b就好了
x = y';
y = x' - a / b * y';那这用递归实现是个倒序遍历，
一下就是代码
#include <iostream>
using namespace std;
int x, y;
void exgcd(int a, int b) {
if (b == 0) {
x = a;
y = 0;//y为任意值都有解
}
else {
exgcd(b, a % b);
int x0 = x, y0 = y;
x = y0;
y = x0 - a / b * y0;
}
}
int main() {
int a, b;
cin >> a >> b;
exgcd(a, b);
cout << x << ' ' << y;
return 0;
}