30 扩展欧几里得算法+中国剩余定理

1 扩展欧几里得算法
 

/*
学acwing的算法基础课学来的，喜欢的话多多支持呀。
*/
//扩展欧几里得算法求 a*x+b*y=gcd(a,b)求x,y
#include
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{
if(!b)//假如b为0 ，则x为1，y为0
{
x=1,y=0;
return a;//返回最小公倍数为a
}
int d=exgcd(b,a%b,y,x);//d为最小公倍数
y-=a/b*x;//根据推理得来的，y更新为这个
return d;//返回最小公倍数
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int a,b,x,y;
scanf("%d%d",&a,&b);
exgcd(a,b,x,y);

30 扩展欧几里得算法+中国剩余定理最先出现在Python成神之路。