真TMD难啊！！！！我真的想*欧几里得

好吧难还是得学啊。。。9九月就初赛

①欧几里得算法

这东西很简单啊。。就记个结论就可以了

1
gcd(a,b)=gcd(b,a%b)

然后就没有了

②欧几里得算法的应用

这东西就是用来求最大公约数的

1
2
3
4
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}

接下来的才是难点

③欧几里得算法拓展

欧几里得算法拓展用于求

ax+by=gcd⁡(a,b)\text{ax}{+ by} = \gcd\left( a,b \right)

的其中一组解

具体过程如下：

 ax1+by1=gcd⁡(a,b)\text{\ ax}_{1}{+ by}_{1} = \gcd\left( a,b \right)

利用欧几里得公式

=>bx2+(a%b)y2=gcd⁡(b,a%b)= > \text{bx}_{2}{+ (a\% b)y}_{2} = \gcd\left( b,a\% b \right)

可以重复利用欧几里得公式，到最后一层b会变成0

=>(…)xi+(…)yi =gcd⁡(…,0)= > (\ldots)x_{i} + (\ldots)y_{i}\ = \gcd\left( \ldots,0\right)

最终b变成0时，最后一层的x与y可以求出来

axi+byi=gcd⁡(a,0)=a ∴xi=1,yi=0{\text{ax}}_{i}{+ by}_{i} = \gcd\left( a,0 \right) = a\ \therefore x_{i} = 1,y_{i} = 0

现在看上下层的回溯关系

a%b=a−[ab]×ba\% b = a - \lbrack\frac{a}{b}\rbrack \times b

但是第一步先要利用上面这个公式

ax1+by1=bx2+(a%b)y2\text{ax}_{1}{+ by}_{1} = \text{bx}_{2} + {(a\% b)y}_{2}

=bx2+(a−[ab]×b)y2= bx_{2} + \left( a - \left\lbrack \frac{a}{b} \right\rbrack \times b \right)y_{2}

=ay2+bx2−[ab]×b×y2= ay_{2} + bx_{2} - \left\lbrack \frac{a}{b} \right\rbrack \times b \times y_{2}

=ay2+b(x2−[ab]×y2)= ay_{2} + b(x_{2} - \left\lbrack \frac{a}{b} \right\rbrack \times y_{2})

所以上下层的x与y的关系:

xi=yi+1yi=xi+1−[ab]×yi+1x_{i} = y_{i + 1}y_{i} = x_{i + 1} - \left\lbrack \frac{a}{b} \right\rbrack \times y_{i + 1}

之后一层一层回退，求出x1与y1就是最终结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void exgcd(int a,int b)
{
    if(b==0)
    {
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b);
    k=x;
    x=y;
    y=k-a/b*y;
    return;
}

④欧几里得算法拓展的应用

欧几里得还可以求解下面的这种式子或者逆元也可以（逆元我实在不会啊）

ax+by=max + by = m

首先要判断这种式子有没有解

所以我们要介绍一下贝祖定理：

1
如果a、b是整数，那么一定存在整数x、y使得ax+by=gcd(a,b)。

换句话说，如果ax+by=m有解，那么m一定是gcd(a,b)的若干倍。

有一个直接的应用就是 如果ax+by=1有解，那么gcd(a,b)=1(所以欧几里得还可以用来求满足 ax mod b = 1 的最小正整数 x）

反正就是如果那个式子有解，把a与b同时乘k倍，使得gcd(ak,bk)=m

再用之前的方法求解就可以了（指求一组解，不可能求出所有解的）