Центр «Поиск» г. Ставрополя. Лето 2010

#include <cstdio>
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int gcd(int a,int b,int &x,int &y){
    if(b==0) {x=1;y=0;return a;}
    int x1,y1,d;
    d=gcd(b,a%b,x1,y1);
    x=y1;
    y=x1-(a/b)*y1;
    return d;
}
int main(){
    printf("GCD=%d\n",gcd(221,323));
    int x,y;
    int d=gcd(221,323,x,y);
    printf("%d=%d*%d+%d*%d",d,221,x,323,y);
    return 0;
}