Modular Inverse（模線性方程）

http://acm.sdut.edu.cn:8080/vjudge/contest/view.action?cid=89#problem/F

求解 ax≡1 (mod m).

原式相當於 ax(mod m) = 1(mod m),那麼 ax-1 是m的倍數。 設ax-1 = my ——> ax - my = 1。

該式有解的前提是 1 是 a和m的最大公約數的倍數，因此 a 和 m 互質，方程有唯一解。

然後再用擴展歐幾裡得。注意m等於1的時候x的最小值是1。

#include 
#include 
#include 
using namespace std;

int gcd(int a, int b)
{
	if(b == 0)
		return a;
	return gcd(b,a%b);
}

int extend_gcd(int a, int b, int &x, int &y)
{
	if(b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}

	int r = extend_gcd(b,a%b,y,x);
	y -= x*(a/b);
	return r;
}

int main()
{
	int test;
	int a,m;
	scanf("%d",&test);
	while(test--)
	{
		scanf("%d %d",&a,&m);
		if(m == 1)
		{
			printf("1\n");
			continue;
		}

		if(gcd(a,m) != 1)
		{
			printf("Not Exist\n");
			continue;
		}

		int x,y;
		extend_gcd(a,m,x,y);
		if(x < 0)
			x += m;
		printf("%d\n",x);
	}
	return 0;
}