扩展欧几里得

关键词：

对于方程 ax+by=c（x,y为整数），当且仅当 c%gcd（a,b）==0 时，（x,y）有解（见证明3），且有gcd(a,b)组解。

求出方程的一个解x，方程的最小正整数解x0 = (x%(b/gcd(a,b) ) + b/gcd(a,b)) % b/gcd(a,b) (见证明4)

那么 exgcd（int a,int b,int &x,int &y）为求解该方程的函数，这个函数的返回值为 gcd(x,y)，代码如下

int exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x = 1; //解释见证明1
        y = 0; //解释见证明1
        return a;
    }

    else
    {
        int r = exgcd(b,a%b,y,x);  //解释见证明2
        y -= a/b*x;  //解释见证明2
        return r;
    }
}

相关证明：

　　证明1：当b=0时，gcd（a,b）= a,那么有 ax=a， 得x=1，y=0。

　　证明2：有裴蜀定理得知：a*x1 + b*y1 = gcd(a,b) 一定成立，

　　　　　  那么得：b*x2 + (a%b)*y2 = gcd(a,b) 

　　　　　  那么得：b*x2 + (a - a/b*b)*y2 = gcd(a,b)

　　　　　  那么得：b*x2 + a*y2 - a/b*y2*b = gcd(a,b)

　　　　　  那么得：a*y2 + b(x2 - a/b*y2) = gcd(a,b)

　　　　　  因为：a*x1 + b*y1 = gcd(a,b)

　　　　　  所以： x1= y2,y1 = (x2 - a/b*y2)

　　证明3： 结论 对于方程 ax+by=c（x,y为整数），当且仅当 c%gcd（a,b）==0 时有解

　　　　　　设 f = c mod (gcd(a,b)),那么f的取值范围应为 ： 0 <= f < gcd(a,b)

　　　　　　有裴蜀定理知道：ax + by = gcd(a,b)

　　　　　　可设：k*gcd(a,b) + f = c

　　　　　　那么：k*a*x + k*b*y + f = c

　　　　　　若 f != 0,因为0 <= f < gcd(a,b)，所以 f = m*a(m为整数)不成立，所以 k*a*x + k*b*y + ma = c 不成立

　　　　　　所以 f应为0，那么 c mod (gcd(a,b)) 应为 0。

　　证明4：设c = gcd(a,b)，相邻的两组解之间的间隔为dx

　　　　　　得：a*x = d(mod b),

　　　　　　　　a*(x+dx) = d(mod b)

　　　　　　两个式子相减得 ： a*dx % b  = 0

　　　　　　a*dx 是b的整数倍，也是a的整数倍,所以lcm(a,b)所对应的dx值最小

　　　　　　lcm(a,b) = a*b/c

　　　　　　所以 a*dx = a*b/c，所以 dx = b/c

　　　　　　所以最小解x0为：(x%dx + dx)%dx，(x为已经求出的一个解)

欧几里得和扩展欧几里得

...详细，http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html欧几里得算法，就是人们常说的辗转相除法，比较好理解，主要作用是求两个数最大公约数，最小公倍数也可方便的求出1intgcd(inta,intb)2{3returnb==0?a:gcd(b,a%b);4}ViewCod 扩展... 查看详情

数论扩展欧几里得算法

扩展欧几里得  上回刚写完欧几里得，那现在还有一个东西叫拓展欧几里得：  扩展欧几里得法是一个在求解同余方程等问题上的一个很好的方法，其具体功能如下：  在已知(a,b)时，求解一组(p,q)使得p*a+q*b=... 查看详情

同余|欧拉定理|费马小定理|扩展欧拉定理|扩展欧几里得算法

目录同余基本定理欧拉定理费马小定理扩展欧拉定理扩展欧几里得算法同余基本定理欧拉定理若a,m互质，则[a^varphileft(might)equiv1left(modmight)]应用令，，这两个数是互素的。比5小的正整数中与5互素的数有1、2、3和4，所以。计算：... 查看详情

扩展欧几里得

voidexgcd(inta,intb,int&x,int&y){if(b==0){ x=1;y=0; return; } exgcd(b,a%b,y,x); y-=a/b*x;} 查看详情

扩展欧几里得exgcd

ElementaryNumberTheory -ExtendedEuclidAlgorithmTimeLimit:1sec,MemoryLimit:65536KB JapaneseversionishereExtendedEuclidAlgorithmGivenpositiveintegers a and b,findtheintegersolut 查看详情

扩展欧几里得

不得不说，我有种不好的预感，如果考试考到这种裸的数学定理，怕是要完。原网址：http://blog.csdn.net/zhjchengfeng5/article/details/7786595扩展欧几里德算法  谁是欧几里德？自己百度去  先介绍什么叫做欧几里德算法 ... 查看详情

扩展欧几里得算法

用途当我们已知$(a,b)$扩展欧几里得算法可以求出满足$p*a+q*b=GCD(a,b)$的$(p,q)$解集$GCD(a,b)$表示$a,b$的最大公约数 前导知识$GCD(a,b)=GCD(b,a\%b)$$GCD(a,0)=0$$a\%b=a-a/b*b$ 推导过程其实扩展欧几里得的推导过程挺自然的$p*a+q*b$$=GCD(a,b)$$=... 查看详情

扩展欧几里得算法

https://zh.wikipedia.org/wiki/扩展欧几里得算法 用类似辗转相除法，求二元一次不定方程的整数解。然后把它们改写成“余数等于”的形式//式1//式2//式3然后把它们“倒回去”//应用式3//应用式2//应用式1得解。这个过程可以用矩阵... 查看详情

扩展欧几里得算法

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

数论初步——扩展欧几里得算法

具体内容见紫书p313-p314一、扩展欧几里得算法思想：找出一对整数(x,y)，使得ax+by=gcd(a,b) 举例：当“a=6,b=15”时，gcd(6,15)=3，故可以得到解“x=3,y=-1”，当然还有其他解“x=-2,y=1”。程序：/* 扩展欧几里得算法 */voidgcd(inta,intb,int... 查看详情

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

1intgcd(inta,intb)23returnb?gcd(b,a%b):a;//最后返回的a为最大公约数4 扩展欧几里得求逆元：51nod12561#include<iostream>2#include<stdio.h>3#include<string.h>4usingnamespacestd;5intd,x,y;6//ax+by=1(x为a 查看详情

hdursa扩展欧几里得

ProblemDescriptionRSAisoneofthemostpowerfulmethodstoencryptdata.TheRSAalgorithmisdescribedasfollow:>choosetwolargeprimeintegerp,q>calculaten=p×q,calculateF(n)=(p-1)×(q-1)>chooseanintegere(1&l 查看详情

扩展欧几里得

voidny(intx,inty,int&a,int&b)if(y==0)a=1;b=0;elseny(y,x%y,a,b);intt;t=a;a=b;b=t-x/y*b; 查看详情

thebalancepoj2142扩展欧几里得

DescriptionMs.IyoKiffa-Australishasabalanceandonlytwokindsofweightstomeasureadoseofmedicine.Forexample,tomeasure200mgofaspirinusing300mgweightsand700mgweights,shecanputone700mgweightonthesideofthemedi 查看详情

c++中扩展欧几里得算法的递归到底发生了啥？

】c++中扩展欧几里得算法的递归到底发生了啥？【英文标题】：Whatexactlyhappensinsideextendedeuclideanalgorithm\'srecursioninc++?c++中扩展欧几里得算法的递归到底发生了什么？【发布时间】：2016-03-0906:20:53【问题描述】：我知道什么是扩展... 查看详情

扩展欧几里得

...明：本文中的变量若非特别说明，均指整数。定义：扩展欧几里得算法是用于解决一类形如求解a*x+b*y=c中(x,y)，或者形如a*x≡b(modc)中x的问题。引理（裴蜀定理）：不定方程a*x+b*y=gcd(a,b)（x,y为变量）一定有无数个解。证明：先证... 查看详情

poj2142(扩展欧几里得)

TheBalanceTimeLimit: 5000MS MemoryLimit: 65536KTotalSubmissions: 5991 Accepted: 2605DescriptionMs.IyoKiffa-Australishasabalanceandonlytwokindsofweightstomeasureadoseofmed 查看详情

理解扩展欧几里得算法的实现

】理解扩展欧几里得算法的实现【英文标题】：UnderstandingimplementationofExtendedEuclideanalgorithm【发布时间】：2021-12-1316:51:10【问题描述】：经过一些实验和搜索，我想出了以下定义：emcd\'::Integer->Integer->(Integer,Integer,Integer)emcd\'a0... 查看详情