扩展欧几里德算法

#include<stdio.h>
int gcd(int a,int b){
    return a%b==0?b:gcd(b,a%b);
}
int main(){
    printf("%d",gcd(15,18));
    return 0;
}

#include<stdio.h>
#define ll long long
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0){x=1;y=0;return a;}
    ll r=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return r;
}
int main(){
    ll a,b,ans,x,y;
    scanf("%lld%lld",&a,&b);
    ans=exgcd(a,b,x,y);
    printf("(%lld) * (%lld)+(%lld) * (%lld)=%lld",a,x,b,y,ans);
    return 0;
}