P1082 同余方程

这道题是一个非常明显的扩展欧几里得的题，所以只要你懂扩展欧几里得算法这道题应该还是比较简单的。

先来给一个传送门：P1082 同余方程

解题思路如下：我们把原题中的式子变一下形状

ax-1=by

ax-by=1

因为我们要明白其实我们要求的东西是x所以这里y不产生影响，所以我们只需要假装没有看到那个减号，偷偷的把减号收到y里面，那么原式就可以变成

ax+by=1

又因为数据一定有解，所以我们根据欧几里得定理，ax+by=gcd(a,b)所以a,b一定互质。

所以这道题就这样搞定了，但是最后要注意的是，我们最后求的东西是x的最小值，因为我们用这个扩展欧几里得算法只能解出一个特解，所以不排除可能性，x有可能是一个负数，或比我们的最小值大，所以我们只需要每次用x-b（这里因为a,b互质，所以不用减b/gcd（a，b）），如果小就+b，然后这道题就做完了，下面放上AC代码：

#include<bits/stdc++.h>
using namespace std;
void exgcd(int a,int b,int &x,int &y)
{
	if(a==0)
	{
		x=0;y=1;
	}
	else
	{
		exgcd(b%a,a,x,y);
		int swap;
		swap=x;
		x=y-(b/a)*x;
		y=swap;
	}
}
int main()
{
	int aa,bb,xx,yy;
	scanf("%d%d",&aa,&bb);
	exgcd(aa,bb,xx,yy);
	while(xx>=0&&xx-bb>=0)xx-=bb;
	while(xx<0)
	{
		xx+=bb;
	}
	printf("%d",xx%bb);
	return 0;
}

谢谢采纳！