当前位置:首页 > C++知识 > 正文内容

【算法】扩展欧几里得算法

亿万年的星光2年前 (2023-01-08)C++知识881

一、欧几里得算法

我们前面学过求最大公约数的算法:欧几里得算法(又叫辗转相除法) ,一般缩写是gcd,在C++中经常写成如下形式:

int gcd(int a,int b)

 { 
     if(a%b==0)
         return b;
     else
         return gcd(b,a%b);
 }

原理就是代码中比较核心的 gcd(b,a%b),这个定理用文字描述就是:

用a除以b(这里是a>b,当然,在程序编程中,求两个数的最大公约数,可以不限a和b的大小,a<b也就是多一次循环)得到结果q和余数r,再用除数b除以余数r 再得到一个余数,再用除数除以余数,…如此循环,直到余数为0,那么此时的除数就是最大公因数。

想要证明gcd(a,b) = gcd(b,a%b),需要简单了解下面两个引理:

  • 若d是a和b的公约数,那么d也是b和c的公约数(c为a%b)

  • 若d是b和c的公约数(c为a%b),那么d也是a和b的公约数

这两个引理的是什么意思呢,拿第一个来说;

假设一个数d是a的因子,也就是a=m*d,同时也是b的因子,b=n*d,那么a%b = a-w*b =  (m-w*n)*d;

由此可得,a的因子集合、b的因子集合和c的因子集合是相同的;

然后利用上述定理当余数为0的时候,除数就是最大公约数;


二、扩展欧几里得算法

    从字面上看,扩展欧几里得算法就是把欧几里得算法进行了扩展,不仅能求a和b的最大公约数,还其他功能,比如:

  • 求ax+by=m的任意一组解,最小整数解。

  • 求模逆元(模反元素)


为了了解学习上面的公式,需要先了解一个裴属定理


裴属定理】:

对于任意正整数a,b,必有非零整数x,y,使得  ax+by= d。其中,d=gcd(a,b)。

显然有 ax` + by` = k * d ,即 x` =k * x  ,  y`= k* y 。

简言之:ax+by能够取到a和b的最大公约数的整数倍。

简单推论:

如果 a,b互质,即gcd(a,b)=1,则ax+by可以取到任意正整数。


知道了上面的定理,我们求ax+by=m就可以判断是否有解,如果有解,那么m一定是gcd的若干倍。

那么,参考的代码模板如下:

C语言版:

 int gcdEx(int a,int b,int*x,int*y)
{
    if(b==0)
    {
        *x=1,*y=0 ;
        return a ;
    }
    else 
    {
        int r=gcdEx(b,a%b,x,y);
        /* r = GCD(a, b) = GCD(b, a%b) */
        int t=*x ;
        *x=*y ;
        *y=t-a/b**y ;
        return r ;
    }
}

C++版:

// 求x, y,使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;   //到达递归边界开始向上一层返回
    }
    int d = exgcd(b, a % b, x, y);
    int temp=y;    
    y=x-(a/b)*y;
    x=temp;
    return d;
}


上面的这段代码的解释是:

首先,当递归到达边界时,余数b==0,除数a就是最大公约数,此时可以得出方程的一组解:

x=1, y=0   //   a*1+b*0= gcd(a,b)

注意在递归中永远都是先得到上一层的结果状态。

假设栈中当前层得到的解是x1,y1, 那么我们递归后带入下一层:

b*x1 + (a%b)*y1 = gcd(a,b)
 ->  b*x1 + (a- (a/b)*b ) *y1 =gcd(a,b)
 ->  a*y1 + b*(x1- (a/b) *y1) =gcd(a,b)

显然,由上一层的解x1,y1,可以推出下一层x,y的状态

x=y1
y=x1-(a/b)*y1


通解形式:

  • x=x0+b/gcd(a,b) * n  (相当于x每次可以增减:b/gcd的整数倍) 

  • y=y0+a/gcd(a,b) * n  (相当于y每次可以增减:a/gcd的整数倍)    《注意:x求出来后,y通常由x代入方程求得》

最小正整数解:

  • x=(x+b/gcd*n)%(b/gcd) = x%(b/gcd)     (b/gcd(a,b)应取正)

  • 若x<=0,则x+=b/gcd


应用:

  • 解不定方程

  • 求逆元

  • 求解线性同余方程

扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【题解】最短路径问题

【题目描述】平面上有n个点(n≤100),每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。若有连线,则表示可从一个点到达另一个点,即两点间有通路,通路的距离为两点间的直线距离。现...

数组的不确定长度输入

0.前言我们在学习数组的时候一般都会告诉你数组的长度,然后for循环去遍历。但是有一类问题是没有n的,也就是没有告诉长度的。1.方法第一种:(数组)#include<iostream>...

进制转换类问题汇总

二进制转十进制十进制转二进制十进制转M进制(M一般小于16)M进制转十进制M进制和N进制互转...

2021 年青岛市程序设计竞赛试题(小学组)决赛

2021 年青岛市程序设计竞赛试题(小学组)决赛

1.方程求解【描述】输入正整数 a,b,c。求有多少组 x 和 y 满足 a*x+b*y=c 。x 和 y 都是非负整数。【输入】一行,包含三个正整数 a,b,c,两个整数之间用单个空格隔开。【输出】...

C++中箭头指针的含义及用法

C++中箭头指针的含义及用法

0.前言c++中我们在一些程序中看到箭头 p—>stu 类似于这样的表示。今天就简单来解释一下点运算和箭头运算。1.点运算常见的点一般出现在结构体中,比如下面的代码:#include<io...

指针(三):指针与函数

1.交换的例子#include<iostream> #include<cstdio> #include<cstring> using namespa...