int A = a; int X_ = 0; int X = 1; // 1 while (true) { int Q = a / b; // 2 int R = a % b; if (R != 0) //3 { a = b; //4 b = R; int tmp = X; X = X_ - Q * X; X_ = tmp; } else if (X < 0) { //3 return X + A; } else //3 return X; } } int main() { int a, b; cin >> a >> b; cout << GDB(a, b) << endl; system("PAUSE"); }