欧几里得算法与拓展欧几里得算法（2）

点赞过5马上更新下一期

一、裴蜀定理

本文含有少量$Latex$，可能导致加载过快！！！

具体内容：

有一对正整数$a$, $b$，则一定存在非$0$整数$x$, $y$，使得$a\times x + b \times y = (a, b)$

真实神奇啊。

那让我们试着来证明一下8。

假设存在一个$x$和$y$，让$a \times x + b \times y = d$

那$d$一定是$(a, b)$的倍数。

这个很显然吧。

使用构造法：就是扩展欧几里得算法。

这时候，聪明的小朋友就会说了：“啊，cht，你咋构造啊？”，我没法构造，但我有电脑。（

二、扩展欧几里得算法

那我们可以把它看成扩展的这个欧几里得算法啊，因为他是要求出我们这个系数的。

当然，如果你忘了，可以去看一下这一片blog:gcd

那我们来康一下怎么写。

首先啊，这个明显是要用这个层层嵌套的写法，把欧几里得的板子改一改就可以了。

嵌套的函数必须有一个终止条件，此时既然要落实改板子，就要落实到底，我们一样用$b$是否等于$0$作为边界条件。

然后我们思考一下当边界成立时，就是$b = 0$时，我们要如何处理。

此时$b = 0$，那么在这时，我们考虑$x$和$y$，不过最后还是要$return$ $a$啊，这个不能忘记。

那$a$的系数也就是$x$，此时我们要求的就是$(a, 0)$，即$a$和$0$的最大公约数，它是$a$。

此时这个代数式就是：$ax + 0y = a$。

解有很多，但是我们给一组方便计算的就可以了，$x = 1, y = 0$。

if(!b)
{
    x = 1, y = 0;
    return a;
}

我们递归求解。

先把$x,y$翻转一下，然后记录在一个变量$d$里。

这时候有的小朋友就会问了，为啥你要翻转呢？

听我解释一下。

当我们的一串递归做完，我们的$exgcd(b, a \mod b, y, x)$就已经算出来了。

此时这几个变量满足$d = by + (a \mod b) * x = (b, a \mod b) = (a, b)$

首先，$a \mod b = a - \lfloor{\frac a b}\rfloor \times b$

来证明一下。

$a \div b = \lfloor {\frac a b} \rfloor ...... p$，求$p$

然后就能一眼瞪出结论了。

接着我们代入，可得：

$b \times y + (a - \lfloor {\frac a b} \rfloor \times b) \times x = d$

整理可得：

$a \times x + b \times (y - \lfloor {\frac a b} \rfloor \times x) = d$

那么在代码里我们的$y$就要$-= a \div b \times x$

最后$return$ $d$就可以了。

完整板子：

int exgcd(int a, int b, int &x, int &y)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

浓缩着思维的精华啊。

不过一定要记得用引用传。

好上板子题。

给定$n$对正整数$a_i,b_i$，对于每对数，求出一组$x_i,y_i$，使其满足$a_i\times x_i+b_i\times y_i=gcd(a_i,b_i)$。

输入格式

第一行包含整数$n$。

接下来n行，每行包含两个整数$a_i,b_i$。

输出格式

输出共n行，对于每组ai,biai,bi，求出一组满足条件的$x_i,y_i$，每组结果占一行。

本题答案不唯一，输出任意满足条件的$x_i,y_i$均可。

数据范围

$1≤n≤10^5$
$1≤a_i,b_i≤2∗10^9$

输入样例：

2
4 6
8 18

输出样例：

-1 1
-2 1

直接贴代码了：

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int exgcd(int a, int b, int &x, int &y)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int main()
{
    int n;
    cin >> n;
    while(n --)
    {
        int a,b ,x ,y ;
        cin >> a >> b;
        exgcd(a, b, x, y);
        cout << x << ' ' << y << endl;
    }
}

三、题目

留下一道题目大家回去写一下试一试，下次讲。

论如何合理的解出xxs同余方程

好了今天的分享就到这里了。

这是我的全部分享

bye~

最后说一下，花了2天更新出来的，可能会有一点点短qwq