扩展欧几里德算法~易懂版

之前一直知道扩展欧几里德算法的实现代码,但是原理一直还是模模糊糊,看了很多终于明白了,于是决定写一篇来记录下自己的思路。

下面实现的其他定理就不再多解释了,主要讲扩展欧几里德算法。

扩展欧几里德算法就是用来求 Ax+By=K 的一组解,  A,B,K 都是已知常量,求解 x, y.

 

首先,根据“贝祖等式“可知,

        Ax1+By1=gcd(A,B).

 

所以我们可以接着推出

       C =A%B.

       Bx2 + Cy2 = gcd(B,C)

        =  Bx2 + (A%B)y2 = gcd( B, A%B ).

 

然后我们再接着推个用到的

      A%B=[A-(A/B)*B]. //这一步要注意下,这里的  ‘A/B’是计算机中的A/B,不保留小数的 

 

最后,我们可以来总推了

      Ax1 + By1 = gcd( A, B ) .

      C=A%B.

      Bx2 + Cy2 = gcd( B, C ).

      gcd( A, B ) = gcd( B, C ).//划重点

   所以

      Ax1 + By1 = Bx2 + Cy2

      Ax1 + By1 = Bx2 + ( A%B )y2

      Ax1 + By1 = Bx2 + [ A - (A/B) * B ]y2

      Ax1 + By1 = Bx2 + Ay2 - [ (A/B) *B]y2

   根据恒等定理得

      Ax1 = Ay2

      By1 = Bx2 -  B*[ (A/B) *y2 ] = B * [ x2 - (A/B)*y2 ]

   所以

      x1 = y2

      y1 = x2 - (A/B)*y2

  

   仔细观察下这其实就是个递推的过程

      因为 x1要从 y2得来 ,   y1要从  x2 - (A/B)*y2得来

          而 x2 要从 y3 得来 , y2要从  x3 - (A/B)*y3得来

       .........................................................................

         最终Xn-1 要从 Yn得来,Yn-1 要从 Xn - (A/B)*Yn

       //注意,这里的A和B的值, 每次都不一样, A 和 B 不断的替换为 A=B , B=A%B,其实就是gcd的参数变换

   那么这个递推的边界在哪里呢?

      假设 A>0  B=0

      则  gcd( A, B )=A.

      则  Ax + By =gcd ( A,B )

      可以推出  x=1, y=0.

      那么边界就是当 B=0的时候,  赋值 x=1,y=0 然后返回

 

————————————————————————————————————————分割线————————————————————————————————————————

 

下面给出两个实现代码,一个是简单流程实现版,一个是代码简化版,建议看懂第一个 然后 用 第二个 

 

//简化版
int gcd_pro(int A, int B, int &x, int &y) { if (B == 0) { x = 1; y = 0; return A; } else { int ans; int x_temp, y_temp; x_temp = x; y_temp = y; ans=gcd_pro(B, A%B, x_temp, y_temp); x = y_temp; y = x_temp - (A / B)*y_temp; return ans; } }

 

 

//白书版
int gcd_pro(int A, int B, int &x, int &y) { if (B == 0) { x = 1; y = 0; return A; } else { int ans; ans = gcd_pro(B, A%B, y, x); y -= (A / B)*x; return ans; } }

 

不过,我们经常性是要解决  Ax + By=C 这样的方程,知道了 Ax + By = gcd(A,B)的解又有什么用呢?

没关系,还是简单数学推导:

    Ax + By = C

    Ax + By = [C * gcd(A,B)] / gcd(A,b)

    A*[ x * C / gcd(A,B) ]  +  B*[ y* C / gcd(A,B) ] = gcd( A, B )

 

这样你看,原本的 x 变成了   x * C / gcd(A,B)

这样你看,原本的 y 变成了   y* C / gcd(A,B) 

 

所以,我们只要把  Ax + By = gcd(A,B) 得出的 x 和 y,

乘等于 C / gcd(A,B) 就得到 Ax + By = C 的解

 

下面给出例子

 

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
using namespace std;

int gcd_pro(int A, int B, int &x, int &y)
{
    if (B == 0)
    {
        x = 1;
        y = 0;
        return A;
    }
    else
    {
        int ans;
        ans = gcd_pro(B, A%B, y, x);
        y -= (A / B)*x;
        return ans;
    }
}

int main() 
{
    int ans;
    int x_ans, y_ans;
    int A_ans, B_ans, C_ans;

    x_ans = y_ans = 0;
    cin >> A_ans >> B_ans >> C_ans;

    ans=gcd_pro(A_ans, B_ans, x_ans, y_ans);

    x_ans *= ans;
    y_ans *= ans;

    cout << ans << endl << x_ans << ' ' << y_ans << endl;

    return 0;
}

 

上一篇:数论杂谈——欧几里得算法及扩展欧几里得


下一篇:NOI / 2.2基本算法之递归和自调用函数——7592:求最大公约数问题