Wikioi 1200 - 同余方程

1200.c

/* Wikioi - Problem 1200 Equation. by Abreto. */
#include <stdio.h>
#define ABS(x)	( ((x)>0) ? (x) : (-(x)) )

int exgcd(int m, int n, int * x)
{
	int q = 0;
	int x0 = 1, x1 = 0;
	int t = 0;
	
	while(n != 0)
	{
		q = m / n;
		t = m; m = n; n = t % n;
		t = x0; x0 = x1; x1 = t - q*x1;
	}

	*x = x0;
	return m;
}

int main(void)
{
	int a = 0, b = 0;
	int g = 0, x = 0;
	int t = 0;

	scanf("%d %d", &a, &b);
	g = exgcd(a, -b, &x);
	x *= g;
	t = ABS(b/g);

	while( x < 0 ) x += t;
	while( x > t ) x -= t;

	printf("%d\n", x);
	return 0;
}