Расширенный алгоритм Евклида для нахождения НОД.

[Fantom.as]

Ребят помогите написать программу, реализующую расширенный алгоритм Евклида.
Первая часть более понятна, но есть пробелы. А с представлением НОД через d = a*u0+ b*v0.

[Mad_Cat]

расширенный алгоритм евклида

[Fantom.as]

Забыл добавить, нужен код на СИ.

[Mad_Cat]

Забыл добавить, нужен код на СИ.

Исходник на Си.

[Fantom.as]

Я этот исходник видел, но разобраться в его работе не смог.

[Fantom.as]

Помогите разобраться с этим фрагментом кода программы

void extended_euclid(long int a, long int b, long int *x, long int *y, long int *d)
{
long int q, r, x1, x2, y1, y2;
if (b == 0) {
*d = a, *x = 1, *y = 0;
return;
}
x2 = 1, x1 = 0, y2 = 0, y1 = 1;

while (b > 0) {

     q = a / b, r = a - q * b;

     *x = x2 - q * x1, *y = y2 - q * y1;

     a = b, b = r;

     x2 = x1, x1 = *x, y2 = y1, y1 = *y;

}

*d = a, *x = x2, *y = y2;

Как происходит вычисление представления НОД в этом фрагменте?