>>578
#include <stdio.h>

int exgcd(int a, int b, int* x, int* y)
{
int x0 = 1, x1 = 0;
int y0 = 0, y1 = 1;
int c, q, x2, y2;
while (b > 0) {
q = a / b;
c = a - q * b; a = b; b = c;
x2 = x0 - q * x1; x0 = x1; x1 = x2;
y2 = y0 - q * y1; y0 = y1; y1 = y2;
}
*x = x0; *y = y0;
return a;
}

int main()
{
int a = 243, b = 117;
int x, y, c = exgcd(a, b, &x, &y);
printf("%d * x + %d * y = c\n", a, b);
printf("x = %d + %d * k, ", x, b / c);
printf("y = %d - %d * k, ", y, a / c);
printf("c = %d, where k is integer\n", c);
return 0;
}