확장된 유클리트 알고리즘 (gcd 최대공약수) 구하기

#include <stdio.h>

int gcd(int a, int b) {

    int c, ax=1, ay=0, bx=0, by=1, cx=0, cy=0;

    c=a%b; 

    cx=ax-a/b*bx; 

    cy=ay-a/b*by;

    while(c!=0) {

        a=b; ax=bx; ay=by;

        b=c; bx=cx; by=cy;

        c=a%b;  cx=ax-a/b*bx; cy=ay-a/b*by;

    }

    printf("x=%d y=%d\n", bx, by);

    return b;

}

int main() {

    int a, b;

    printf("두정수: ");

    scanf("%d%d", &a, &b);

    printf("gcd=%d", gcd(a, b));

    return 0;

}