Modular Inverse

http://acm.sdut.edu.cn:8080/vjudge/contest/view.action?cid=89#problem/F
解 ax≡1 (mod m).
原式はax(modm)=1(modm)に相当し、ax−1はmの倍数である.ax-1=my——>ax-my=1とします.
この式の解の前提は1がaとmの最大公約数の倍数であるため,aとmは互いに質的であり,方程式には唯一の解がある.
それからユークリッドを拡張します.注意mが1に等しい場合xの最小値は1です.

#include <stdio.h>
#include <string.h>
#include <algorithm>
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
");
			continue;
		}

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

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