// Обобщенный алгоритм Евклида для поиска наибольшего общего 
// делителя gcd = НОД(u,v) целых положительных чисел u и v 
// и коэффициентов a и b уравнения a*u + b*v = gcd
// Все числа полагаются типа long

// Подстановки упрощающие запись исходного текста
#define isEven(x) ((x & 0x01L) == 0)		// x - четное?
#define isOdd(x)  ((x & 0x01L))			// x - нечетное?
#define swap(x,y) (x ^= y, y ^= x, x ^= y)  // обмен значений x и y

void GenEuclid(long *u, long *v, long *a, long *b, long *gcd)
{
int k; 	// Параметр циклов
long a1, b1, g1; 	// Вспомогательные переменные

// Алгоритм предполагает, что u > v, если u < v, то они переставляются
if (*u < *v) swap(*u, *v);
// Если u = n * 2^k1 или v = m * 2^k2, то перед поиском НОД
// производим сокращение u = u/(2^k), v = v/(2^k),
// где k - минимальное из k1, k2. Показатель k запоминаем.
for (k = 0; isEven(*u) && isEven(*v); ++k){
	*u >>= 1; *v >>= 1;
}
// Задание начальных значений
*a = 1; *b = 0; *gcd = *u; a1 = *v; b1 = *u - 1; g1 = *v;
do {
	do {
		if (isEven(*gcd)){
			if (isOdd(*a) || isOdd(*b)){
				*a += *v; *b += *u;
			}
			*a >>= 1; *b >>= 1; *gcd >>= 1;
		}
		if (isEven(g1) || *gcd < g1){
			swap(*a, a1); swap(*b, b1); swap(*gcd, g1);
		}
	} while (isEven(*gcd));
	while(*a < a1 || *b < b1){
		*a += *v; *b += *u;
	}
	*a -= a1; *b -= b1; *gcd -= g1;
} while (g1 > 0);
while (*a >= *v && *b >= *u){
	*a -= *v; *b -= *u;
}
// производим умножение коэффициентов уравнения 
// на сокращенный ранее множитель 2^k
*a <<= k; *b <<= k; *gcd <<= k;
}

*********** Комментарий к циклам do *****************

Обощенный алгоритм Евклида основан на рекуррентном
вычислении коэфициентов a, b, и gcd уравнения 
	a*u + b*v = gcd.
В качестве первого приближения в случае, когда u > v,
берем уравнение
(1)	1*u - 0*v = u,
то есть a = 1, b = 0, gcd = u.
В качестве второго уравнения берем очевидное равенство
(2)	v*u - (u-1)*v = v, 
то есть a1 = v, b1 = u - 1, g1 = v.
Третье уравнение - такое же очевидное равенство
(3)	v*u - u*v = 0,     
то есть a2 = v, b2 = u, g2 = 0.
Эти уравнения можно складывать, вычитать друг из друга и
и их промежуточных сумм, получая равносильные выражения.
Сложение (1) с (3) означает преобразование
коэффициентов
	a = a + v, b = b + u, gcd = gcd.
Вычитание из (1) уравнения (2) означает преобразование
	a = a - a1, b = b - b1, gcd = gcd - g1.
Если текущее значение gcd четно, а какой-то из коэффициентов
а или b нечетный, то прибавив (3) к (1), получим возможность 
сократить все коэффициенты на 2. Если a и b нечетны, то при
четном gcd значения u и v должны быть также нечетным, так как одно из них обязательно нечетно из-за предваритеьных делений на степень 2. Если a нечетно, а b четно, то u обязано быть четным, тогда v - нечетно. Как только в результате сокращений правая часть (1) станет меньше правой части (2) делаем первое уравнение вторым, а второе - первым путем обмена значений: a c a1, b c b1 и gcd c g1. Такой же обмен делаем, когда gcd нечетно и его дальнейшее сокращение на 2 невозможно, а g1 - четно, и можно выполнить сокращение в уравнении (2). Если gcd > g1 и gcd нечетно, то дальше сокращать коэффициенты нельзя - выходим из внутреннего цикла do. Прибавлением (3) к (1) добиваемся соблюдения уловий a > a1 и b > b1. Затем, вычитая (2) из (1), стремимся уменьшить правую часть уравнения (1) приблизив ее к истинному значению НОД. После каждого вычитания проверяем не равно ли g1 нулю. В этом случае дальнейшее вычитание уже не приведет к изменению правой части (1). При g1 = 0 выходим из внешнего цикла do. В противоположном случае снова входим во внутренний цикл и проверяем возможность дальнейших сокращений уравнений (1) и (2) на 2. По окончании циклов, для того чтобы обеспечить a < v и b < u, вычитаем (2) из (1) столько раз сколько потребуется. ************************************************************ Для того, чтобы проследить последовательность преобразований для конкретных чисел u и v при запуске программы euclid.exe установите флажок "Записать протокол вычислений в файл". При этом все значения a, b, gcd, a1, b1, g1 после каждого изменения будут записаны в файл logf.txt в текущей папке (каталоге). Замечание 1. При установленном флажке брать числа u и v большими, чем 10^7 не рекомендуется. Замечание2. При просмотре файла logf.txt в Блокноте установите в меню "Формат" шрифт "Courier New" или любой моноширинный.