扩展欧几里得算法详解(代码片段)

关键词：

本篇将附上扩展欧几里得算法的思想与推导;

---

对于一个方程(a*x+b*y=gcd(a,b))来说,我们可以做如下的推导:

设有(a*x_1+b*y_1=gcd(a,b));

同时我们有(b*x_2+(a\%b)*y_2=gcd(b,a\%b));

对于这个方程组,我们希望知道的是(x_1,x_2,y_1,y_2)之间的关系,这样我们才可以递归解决这个问题;

我们观察(b*x_2+(a%b)*y_2)这个式子,我们可以将((a\%b))写作((a-lfloorfracab floor*b)),将括号打开常数(a,b)合并,合并之后的结果为(a*y_2+b*(x_2-lfloorfracab floor*y_2)))

由于欧几里得算法的原理(gcd(a,b)==gcd(b,a%b)),我们将两式子联立,对比系数即可得到(x_1=y_2,y_1=x_2-lfloorfracab floor*y_2);

这个递归的边界是什么呢?我们知道,当朴素欧几里得到达边界时,(return gcd(a,0)=a),那么边界条件就是对(a*x_0+b*y_0=a)求解,很显然,此时(x_0=1,y_0=0);

当我们递归求出了一个方程的特解时,如何求出这个方程的通解呢?

方程(a*x+b*y=gcd(a,b))中,如果将x加上一个常数(k_1,y)减去一个常数(k_2),仍然保持原方程成立,那么(x+k_1,y-k-2)就是方程的一个新解,这个k应该如何选择呢?

实际上很简单,(a*(x+k_1)+b*(y+k_2)=gcd(a,b)),打开括号,(a*x+a*k_1+b*y-b*k_2=gcd(a,b)),我们保证原方程成立,就需要(a*k_1==b*k_2),那么显然(k_1=b,k_2=a)是一种合理的情况,但是这样是无法包含所有整数解的,因为我们加上的这个值并非是最小值.

那我们应该加上什么值才行呢?我们发现当(a*k_1==b*k_2=t*lcm(a,b))可以保证得到所有解,于是每次寻找解就可以分别在(x)加上(fracbgcd(a,b),在y减去fracagcd(a,b))就可以了

对于方程(a*x+b*y=c)我们又该如何求解?我们发现如果((c%gcd(a,b)!=0))那么这个方程是无解的,而如果(gcd(a,b)*t==c),我们就可以按上面的方法求解之后对我们的解乘上一个(t(t=fraccgcd(a,b)))

(code:)

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

    if(!b)
    
        x1=1,y1=0;
        return a;
    
    int x2,y2;
    int d=exgcd(b,a%b,x2,y2);
    x1=y2,y1=x2-(a/b)*y2;
    return d;

扩展欧几里得算法(代码片段)

 代码：1longlonge_gcd(longlonga,longlongb,longlong&x,longlong&y)23if(b==0)45x=1,y=0;6returna;78longlongans=e_gcd(b,a%b,x,y);9longlongtmp=x;10x=y;11y=tmp-a/b*y;12returnans;131)扩展欧几里得算法求ax 查看详情

[模板]欧几里得算法/扩展欧几里得(代码片段)

最大公因数（欧几里得算法）$gcd(a,b)=gcd(b\%a,a)$（不一定需要a<b）$gcd(0,b)=b$1inlineintgcd(inta,intb)2returna==0?b:gcd(b%a,a);3扩展欧几里得寻找$ax+by=gcd(a,b)$的一组解x,y（一定存在整数解）$ax+by=gcd(a,b)=gcd(b\%a,a)=(b-lfloorfracba 查看详情

exgcd（扩展欧几里得算法）(代码片段)

定理，证明，少例题其实挺简单。GCD（辗转相除法）定理：\\[\\gcd(a,b)=\\gcd(b,a\\%b)\\]证明：\\[\\text设a=kb+r\\text，则r=a\\bmodb\\]\\[\\text若c\\text是a,b\\text的一个公约数，则c\\mida,c\\midb\\]\\[\\becauser=a-kb\\]\\[\\thereforec\\midr\\]\\[ 查看详情

扩展的欧几里得算法(代码片段)

求解形如ax+by=gcd(a,b)的一组解。#include<bits/stdc++.h>//ax+by=gcd(a,b)x=?y=?usingnamespacestd;intextend_gcd(inta,intb,int&x,int&y)intret,tmp;if(!b)x=1;y=0;returna;ret=extend_gcd(b,a%b,x,y);tm 查看详情

扩展欧几里得算法（exgcd）(代码片段)

...在一对整数x，y满足：a*x+b*y=gcd（a，b）证明如下：　　在欧几里得算法的最后一步：b=0，即：gcd（a，0）=a对于b>0，根据欧几里得算法gcd（a，b）=gcd（b，a%b）。假设存在一对x，y满足：b*x+（a%b）*y=gcd（b，a%b）因为b*x+（a%b）*y=b*... 查看详情

欧几里得算法和扩展欧几里得算法(代码片段)

欧几里得算法基本原理和证明代码实现：#include<iostream>usingnamespacestd;intgcd(inta,intb) returnb?gcd(b,a%b):a;intmain() intx,y; cin>>x>>y; cout<<gcd(x,y)<<endl; return0;扩展欧几里得算法原理代码实现：#include<iostream>usingnamespac... 查看详情

扩展欧几里德算法(代码片段)

0、欧几里德定理一切的基础，自然就是欧几里德定理了。它的形式非常简单（sometimesnaive）gcd(a,b)=gcd(b,amodb)    证明：假设a,b的公约数为g,且$$a=bx+y(x,yinZ)$$则显然有$$gmida,qquadgmidb,qquadamodb=y$$$$ecau 查看详情

扩展的欧几里德算法-hdu2669(代码片段)

TheSkyisSprite. TheBirdsisFlyintheSky. TheWindisWonderful. BlewThrowtheTrees TreesareShaking,LeavesareFalling. LoversWalkpassing,andsoareYou. ............................ 查看详情

简单数论总结2——同余方程与扩展欧几里得算法(代码片段)

...是快要开学赶紧来肝上两篇今日内容——同余方程和扩展欧几里得算法同余同余的定义：若存在两个整数a，b，使得(a-b)MODP为0，则称作a与b在MODP的情况下同余换种通俗的说法，就是，aMODP与bMODP相等 记作  (aequivb(modP))... 查看详情

扩展欧几里得(模板)(代码片段)

 扩展欧几里德算法：  谁是欧几里德？自己百度去  先介绍什么叫做欧几里德算法  有两个数ab，现在，我们要求ab的最大公约数，怎么求？枚举他们的因子？不现实，当ab很大的时候，枚举显得那么的na&... 查看详情

扩展欧几里得算法（双六游戏）(代码片段)

题目大意：一个双六上面有向前向后无限延续的格子，每个格子都写有整数。其中0号格子是起点，1号格子是终点。而骰子上只有a,b,-a,-b四个整数，所以根据a和b的值的不同，有可能无法到达终点掷出四个整数各多少次可以到达... 查看详情

poj-1061青蛙的约会---扩展欧几里得算法(代码片段)

题目链接：https://cn.vjudge.net/problem/POJ-1061题目大意：两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之... 查看详情

扩展欧几里得与乘法逆元(代码片段)

一。欧几里得算法欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。基本算法：设a=qb+r，其中a，b，q，r都是整数，则gcd(a,b)=gcd(b,r)，即gcd(a,b)=gcd(b,a%b)。递归实现：1intgcd(inta,intb)23if(b==0)4returna;5return6gcd(b,a%b);7优... 查看详情

扩展欧几里得算法+推论(代码片段)

什么是扩展欧几里得？扩展欧几里得算法是建立在欧几里得算法(gcd)之上。首先，我们知道有(a*x+b*y=gcd(a,b))我们怎么求这个(x,y)呢？这时候我们就得使用exgcd算法，我们来推导一下吧！(a*x+b*y=gcd(a,b))(a*x+b*y=gcd(b,a\%b))(a*x+b*y=b*x'+(a-... 查看详情

扩展欧几里得算法(代码片段)

扩展欧几里得算法定义：贝祖定理对于任意整数a,b，存在一对整数x,y,满足ax+by=gcd(a,b)用欧几里得算法计算一组x,y的方法，称作“扩展欧几里得”算法求解思路假设a>b[(1)b=0:gcd(a,b)=a,ax+by=a,则x=1,y=0;][(2)beq0，如图]Codeintexgcd(inta,intb,i... 查看详情

算法knnsvm算法详解！(代码片段)

...来推断这个未知数据的分类KNN的原理步骤计算距离（常用欧几里得距离或马氏距离）升序排列（最近的排前面，最远的排后面）取前K个加权平均K的选取（算法的核心）K太大：导致分类模糊K太小：受个例影响，波动较大如何取K... 查看详情

欧几里得算法(代码片段)

 一、欧几里得算法（辗转相除法）llgcd(lla,llb)if(b==0)returna;elsereturngcd(b,a%b); 二、扩展欧几里得算法在求a，b的gcd的同时求出一组特解x,y满足方程 ax+by=gcd(a,b) voidextgcd(lla,llb,ll&d,ll&x,ll&y)if(!b)d=a;x 查看详情

关于扩展欧几里得(代码片段)

给出两个整数a,b扩展欧几里得可以求出gcd(a,b)，并且能顺带算出一组特解(x,y)，使ax+by=gcd(a,b)。其实扩展欧几里得算法就是收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。原理如下：设a=r0，b=r1，那么根据... 查看详情