同余方程（扩展欧几里得）（C/C++）

ax%b=1,则a和b的最大公约数一定是1。

#include <cstdio>
#include <iostream>
using namespace std;
int a,q;
int x,y;
void exgcd(int a,int b)
{
	if (b==0)
	{
		x=1;
		y=0;
		return ;  //得到gcd(b,0)时到达边界值
	}  //
	else
	{
		exgcd(b,a%b);
		int k=x;
		x=y;
		y=k-(a/b)*y;  //根据上方推出的公式进行递归求出结果
	}
	return ;
}
int main()
{
	scanf("%d%d",&a,&q);  
	exgcd(a,q);
	printf("%lld",(x+q)%q);
	return 0;
}