Now tell you two nonnegative integer a and b. Find the nonnegative integer X and integer Y to
satisfy X*a + Y*b = 1. If no such answer print "sorry" instead.
Input
The input contains multiple test cases.
Each case two nonnegative integer a,b (0<a, b<=2^31)
Output
output nonnegative integer X and integer Y, if there are more answers than the X smaller one
will be choosed. If no answer put "sorry" instead.
Sample Input
77 51
10 44
34 79
Sample Output
2 -3
sorry
7 -3
思路：exgcd 最后X为最小正解
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if(!b) {
x=;y=;return a;
}
ll ans=exgcd(b,a%b,x,y);
ll temp=x;
x=y;
y=temp-a/b*y;
return ans;
}
int main() {
ios::sync_with_stdio(false);
ll a,b,x,y;
while(cin>>a>>b) {
ll g=exgcd(a,b,x,y);
if(g!=) {
cout<<"sorry"<<endl;
} else {
x=(x%b+b)%b;
y=(-a*x)/b;
cout<<x<<" "<<y<<endl;
}
}
return ;
}