求最大公约数问题

#include<iostream>
using namespace std;
int gcd(int a,int b){
	int c=0;
	while(a%b!=0){
		c=a%b;
		a=b;
		b=c;
	}
	return b;
}
int main(){
	int a,b;
	cin>>a>>b; 
	cout<<gcd(a,b);
}

这就是gcd(a,b)的基本用法 在扩展欧几里得里是exgcd(a,b)根据基本用法来解决同余方程，例如同余方程； $x=y;y=x-(a/b)y$ 题解，抄袭可耻，放抄袭；

#include<bits/stdc++.h>
using namespace std; 
long long int x=0,y=1;
long long int exgcd(long long int a,long long int b){
	//gcd(a,b)
	long long int g=exgcd(b,a%b);
	long long int t=x;
	//基本公式
	return g;
}

int main(){
	long long int a,b;
	cin>>a>>b;
	//这一部分自己思考
	return 0;
}

大家还可以参考青蛙的约会进行巩固，虽然啧啧。 AK天下为大家翻译了题意如下 $青蛙A的出发点坐标是m1,一次能跳m米；青蛙B的出发点坐标是n1,一次能跳n米；跳一圈长l米 青蛙A、B跳了x次$ 最小正整数解 $(m-n)*x≡m1-n1 (mod l) (m-n)*x+l*y=m1-n1$ 扩展欧几里得 $a*x+b*y=c ；若a*x+b*y=c有解，则满足gcd(a,b)/c ；$ 最后，欢迎大家加入https://www.luogu.com.cn/team/97635