#include <iostream>
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

using namespace std;

int fastpow(int x, int n, int m) {
    int res=1;
    if (!n) return 1;
    while (n) {
        if (n&1) {
           res=(res*x)%m;
        }
        x=(x*x)%m;
        n>>=1;
    }
    return res % m;
}

void euclid(int a, int b, *int d, *int x, *int y) {
     int x1,x2,y1,y2,q,r;
     if (b==0) { *d=a; *x=1; *y=0; }
     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;
     }

}

int main() {
    int va,vb,d,x,y;
    cout<<"×èñëî à"<<endl;
    cin>>va;
    cout<<"×èñëî b"<<endl;
    cin>>vb;
    cout<<euclid(va,vb,d,x,y)<<endl;
    getch();
    return 0;
}