12082015

n --> 0
r = m % n; m <-- n; n <-- r;
kq: m;

//1; < 1_ 11
O(log min(a, b)); :v

Pt Diophante ax + by = d giai bang thuat toan Eulic mo rong
a, b: int != 0;
d = GCD(a, b);
--/ k = ax + by
	m = a * xm + b ym ... n .. r;

	voi m = a --> xm = 1; ym = 0;
	    n = b --> xm = 0; ym = 1;

	while (n != 0)
	{
		q = m / n; r = m - q*n; (so du --> tim cap so bieu dien r = pp the)
		(xr, yr) = (xm, ym) - q*(xn, yn)
		m = n && (xm, ym) = (xn, yn); n = r && (xn, yn) = (xr, yr);
	}
	kq: m = a*xm + b * ym;
Toi uu
Tinh x => y; (bo all nghiem y tren code)
--> (xm, (d - a * xm) / b);

Tong quat pt Diophante
pt co nghiem khi: c chia het cho d voi d = GCD(a, b) --> vsn
ax + by = c;
a(x + p) + b(y - q) = c;
--> ap = bq <=> p / q = b / a;
BCNN --> luong lien hiep

HE 2 PT BAC I 2 AN
a1 * x + b1 * y = c & a2 * x + b2 * y = c2;
1. Co vsn R
2. Co vsn N
--> Tim UCLN + kt t/c co no of 2 pt

DIOPHANTE
1 <= x <= (c - b) / a;
	if (x0, y0) ~ no of pt
	x = x0 + kp, y = y - kq; --> dong du ( O(1) );
Nghich dao Modulo
if GCD(a, b) = 1, giai ax + by = 1;