HDU 2669 Romantic【扩展欧几里德】

裸的扩展欧几里德，求最小的X，X=((X0%b)+b)%b,每个X都对应一个Y，代入原式求解可得

#include<stdio.h>

#include<string.h>

typedef long long ll;

ll ex_gcd(ll a,ll b,ll &x,ll &y){

    if(!b){

        x=,y=;

        return a;

    }

    int ans=ex_gcd(b,a%b,y,x);

    y-=a/b*x;

    return ans;

}

void cal(ll a,ll b,ll c){

    ll x,y;

    ll d=ex_gcd(a,b,x,y);

    if(d!=){

        printf("sorry\n");

        return ;

    }

    x=((x%b)+b)%b;

    y=(-a*x)/b;

    printf("%I64d %I64d\n",x,y);

}

int main(){

    ll a,b;

    while(scanf("%I64d%I64d",&a,&b)!=EOF)

        cal(a,b,1ll);

    return ;

}