关键词：
声明：本文中的变量若非特别说明，均指整数。
定义：
扩展欧几里得算法是用于解决一类形如求解a*x+b*y=c中(x,y)，或者形如a*x≡b(mod c)中x的问题。
引理（裴蜀定理）：
不定方程a*x+b*y=gcd(a,b)（x,y为变量）一定有无数个解。
证明：
先证明该方程有解。
将欧几里得算法倒推上去。因为欧几里得算法总会结束，所以方程一定有解。
设a=b*p+q（0<=q<b），则gcd(a,b)=gcd(b,q)。
设b*x‘+q*y‘=gcd(b,q)，则有b*x‘+(a-b*p)*y‘=gcd(b,q)=gcd(a,b)。
整理得a*y‘+b*(x‘-p*y‘)=gcd(a,b)。
所以a*x+b*y=gcd(a,b)可由b*x‘+q*y‘=gcd(b,q)推得。
当q=0时，gcd(b,q)=b，此时(1,0)即为解，算法结束。
又因为算法总会递归到q=0的情况（欧几里得算法），所以该过程一定会结束，方程一定有解。
再证明该方程有无数个解。
设(x,y)为原方程的一个解，则有a*x+b*y=gcd(a,b)，则有a*(x+k*b)+b*(y-k*a)=gcd(a,b)。
所以形如(x+k*b,y-k*a)的二元组均为该方程的解，由k的任意性可知，该方程有无数个解。
原理：
由裴蜀定理，若c不是gcd(a,b)的倍数，直接返回无解，否则设c=gcd(a,b)*p，根据裴蜀定理求得一个解(x,y)，则(p*x,p*y)是该方程的解。
有时题目为了方便判定，会特别规定(x,y)中x或y为最小正整数，此时根据无数个解的求法调整即可。
代码：
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
void exgcd(int a,int b,int &x,int &y)
{
if(!b){x=1;y=0;return;}
int p=a/b,q=a%b,u,v;
exgcd(b,q,u,v);
x=v;y=u-p*v;
}
int main()
{
int a,b,c,x,y,tmp;
scanf("%d%d%d",&a,&b,&c);//ax+by=c
tmp=gcd(a,b);if(c%tmp){cout<<"No Solution
";return 0;}
exgcd(a,b,x,y);x=x*c/tmp;y=y*c/tmp;
x=(b+x%b)%b;//x为最小正整数
printf("%d %d
",x,y);
return 0;
}
欧几里得和扩展欧几里得
...详细，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... 查看详情