青岛做商城网站网站改版中

题目大意：现在告诉你两个非负整数 a 和 b。找到满足 X*a + Y*b = 1 的非负整数 X 和整数 Y。如果没有这样的答案，请写 “sorry”。

思路：这是一道扩展欧几里得模板题，唯一容易错的就是 x 有可能是负数，要把它改成非负数。

a*x+b*y=gcd(a,b)=1成立，所以  a*(x+b)+b(y-a)=1 仍成立。

所以 x = (x+b)%b , y=(1-a*x)/b。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int exgcd(int a,int b,int &x,int &y){if(b==0){x=1,y=0;return a;}int gcd=exgcd(b,a%b,y,x);y-=(a/b)*x;return gcd;
}
signed main(){int a,b;while(cin >> a >> b){int x,y;int gcd=exgcd(a,b,x,y);x=(x+b)%b;if(gcd==1) cout << x << " " << (1-a*x)/b << endl;else cout << "sorry" << endl;}return 0;
}