六种算法基本知识(信息学竞赛中常说的欧几里德算法及拓展欧几里德算法是什么)

六种算法基本知识(信息学竞赛中常说的欧几里德算法及拓展欧几里德算法是什么)(1)

在学习信息学数论部分知识点的过程中,有两个比较重要的算法,那就是欧几里得算法与扩展欧几里得算法。

今天,我们就带大家一起来了解一下这两个算法,看起来相似的算法到底分别是解决了什么问题呢?

欧几里得算法

在学习一种算法前,我认为我们首先应该知道,这种算法是要解决什么问题的。

小学就已经学过了两个数的最大公约数,而欧几里得算法就是为了求出两个数a、b的最大公约数的,这个最大公约数可以表示为gcd(a,b)。

欧几里得算法又称辗转相除法,这个名字已经揭示了它的主要思想:

欧几里德算法的思想基于辗转相除法的原理,辗转相除法是欧几里德算法的核心思想,欧几里德算法说白了其实就是辗转相除法的计算机算法的实现而已。下面我们先说说辗转相除法,辗转相除法的内容:如果用gcd(a,b)来表示a和b的最大公约数,那么根据辗转相除法的原理,有gcd(a,b)=gcd(b,a mod (b)),其中mod()表示模运算,并且不妨让a>b,这样方便于模运算。

引理:gcd(a,b)=gcd(b,a%b)

  证明:

    设 r=a%b , c=gcd(a,b)

    则 a=xc , b=yc , 其中x , y互质

    r=a%b=a-pb=xc-pyc=(x-py)c

    而b=yc

    可知:y 与 x-py 互质

    证明:

  假设 y 与 x-py 不互质

  设 y=nk , x-py=mk , 且 k>1 (因为互质)

   将 y 带入可得

  x-pnk=mk

  x=(pn m)k

   则 a=xc=(pn m)kc , b=yc=nkc

  那么此时 a 与 b 的最大公约数为 kc 不为 k

  与原命题矛盾,则 y 与 x-py 互质

    因为 y 与 x-py 互质,所以 r 与 b 的最大公约数为 c

    即 gcd(b,r)=c=gcd(a,b)

    得证

  当a%b=0时,gcd(a,b)=b

  这样我们可以写成递归形式

它的函数代码只有一行,简单便捷,复杂度O(log n):

代码

int gcd(int a,int b)//欧几里得算法 时间复杂度:O(logn)

{

if(!b) return a;

else return gcd(b,a%b);

}

int gcd(int a,int b)//简化版欧几里得算法 时间复杂度:O(logn)

{

return b?gcd(b,a%b):a;//一行代码就是爽

}

拓展欧几里得算法

用来在已知的a、b中求解一组x、y,使得ax by=gcd(a,b)成立(根据数论相关定理,这组解一定存在)。

了解一下贝祖定理:若存在a、b是整数,则必存在整数x、y,满足ax by=gcd(a,b)。

换句话说,如果ax by=m有解,那么m一定是gcd(a,b)的若干倍。(可以来判断一个这样的式子有没有解)

有一个直接的应用就是 如果ax by=1有解,那么gcd(a,b)=1;

要求出这个最大公因数gcd(a,b),我们最容易想到的就是古老悠久而又相当强大的欧几里得算法:

但是,对于上面的式子ax by=m来说,我们并不仅仅想要知道有没有解,而是想要知道在有解的情况下这个解到底是多少。

所以,扩展欧几里得

当到达递归边界的时候,b==0,a=gcd(a,b) 这时可以观察出来这个式子的一个解:a*1 b*0=gcd(a,b),x=1,y=0,注意这时的a和b已经不是最开始的那个a和b了,所以我们如果想要求出解x和y,就要回到最开始的模样。

初步想法:由于是递归的算法,如果我们知道了这一层和上一层的关系,一层一层推下去,就可以推到最开始的。类似数学上的数学归纳法。

假设当前我们在求的时a和b的最大公约数,而我们已经求出了下一个状态:b和a%b的最大公因数,并且求出了一组x1和y1使得 b*x1 (a%b)*y1=gcd

(注意在递归算法中,永远都是先得到下面一个状态的值)

这时我们可以试着去寻找这两个相邻状态的关系:

首先我们知道:a%b=a-(a/b)*b;带入:

b*x1 (a-(a/b)*b)*y1

= b*x1 a*y1 – (a/b)*b*y1

= a*y1 b*(x1 – a/b*y1) = gcd 发现 x = y1 , y = x1 – a/b*y1

这样我们就得到了每两个相邻状态的x和y的转化,就可以在求gcd的同时对x和y进行求值了。

代码

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

int exgcd(int a,int b,int &x,int &y)//扩展欧几里得算法

{

if(b==0) {

x=1;y=0;

return a; //到达递归边界开始向上一层返回

}

int r=exgcd(b,a%b,x,y);

int temp=y; //把x y变成上一层的

y=x-(a/b)*y;

x=temp;

return r; //得到a b的最大公因数

}

主要应用:

1、乘法逆元

对于缩系中的元素,每个数a均有唯一的与之对应的乘法逆元x,使得ax≡1(mod n)一个数有逆元的充分必要条件是gcd(a,n)=1,此时逆元唯一存在 逆元的含义:模n意义下,1个数a如果有逆元x,那么除以a相当于乘以x。

扩展欧几里得解法:

给定模数m,求a的逆相当于求解ax=1(mod m)这个方程可以转化为ax-my=1 然后套用求二元一次方程的方法,用扩展欧几里得算法求得一组x0,y0和gcd 检查gcd是否为1 gcd不为1则说明逆元不存在 若为1,则调整x0到0~m-1的范围中即可

代码

typedef long long ll;

void extgcd(ll a,ll b,ll& d,ll& x,ll& y){

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

else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); }

}

ll inverse(ll a,ll n){

ll d,x,y;

extgcd(a,n,d,x,y);

return d==1?(x n)%n:-1;

}

2、求解线性同余方程

六种算法基本知识(信息学竞赛中常说的欧几里德算法及拓展欧几里德算法是什么)(2)

来源:https://www.cnblogs.com/lr599909928/p/12704583.html

代码

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <stack>

#include <queue>

#include <vector>

#include <map>

#include <set>

#include <unordered_set>

#include <unordered_map>

#define ll long long

#define fi first

#define se second

#define pb push_back

#define me memset

const int N = 1e6 10;

const int mod = 1e9 7;

using namespace std;

typedef pair<int,int> PII;

typedef pair<long,long> PLL;

int exgcd(int a,int b,int &x1,int &y1){

int x2,y2;

if(b==0){

x1=1,y1=0;

return a;

}

int d=exgcd(b,a%b,x2,y2);

x1=y2,y1=x2-a/b*y2;

return d;

}

int main() {

ios::sync_with_stdio(false);

int n;

cin>>n;

while(n--){

int a,b,m;

int x1,y1;

cin>>a>>b>>m;

int d=exgcd(a,m,x1,y1);

if(b%d) printf("impossible\n");

else printf("%lld\n",(ll)x1*(b/d)%m);

}

return 0;

}

3、求解不定方程

对于不定整数方程pa qb=c,若 c mod Gcd(p, q)=0,则该方程存在整数解,否则不存在整数解。

上面已经列出找一个整数解的方法,在找到p * a q * b = Gcd(p, q)的一组解p0,q0后,p * a q * b = Gcd(p, q)的其他整数解满足: p = p0 b/Gcd(p, q) * t q = q0 - a/Gcd(p, q) * t(其中t为任意整数)

至于pa qb=c的整数解,只需将p * a q * b = Gcd(p, q)的每个解乘上 c/Gcd(p, q) 即可。

在找到p * a q * b = Gcd(a, b)的一组解p0,q0后,应该是得到p * a q * b = c的一组解p1 = p0*(c/Gcd(a,b)),q1 = q0*(c/Gcd(a,b)),

p * a q * b = c的其他整数解满足:

p = p1 b/Gcd(a, b) * t

q = q1 - a/Gcd(a, b) * t(其中t为任意整数)

p 、q就是p * a q * b = c的所有整数解。

用扩展欧几里得算法解不定方程ax by=c;

代码如下:

代码

bool linear_equation(int a,int b,int c,int &x,int &y)

{

int d=exgcd(a,b,x,y);

if(c%d)

return false;

int k=c/d;

x*=k; y*=k; //求得的只是其中一组解

return true;

}

声明:部分资料来源于网络,侵删。

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页