裸的扩展欧几里德,求最小的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 ;
}