JZTXT

欧几里得算法

发布时间 2023-11-01 23:03:59作者: zhuwen
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b){//欧几里得算法 
	if(b==0)	return a;
	return gcd(b,a%b);
}
int exgcd(int a,int b,int &x,int &y){//扩展欧几里得 
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	int d=exgcd(b,a%b,x,y);
	int t=x;
	x=y;
	y=t-a/b*y;
	return d;
} 
signed main(){

	return 0;
}