大淘客官网做的网站打不开,网站建设完成,网站标题权重吗,网站建设方面的书籍推荐题目大意#xff1a;现在告诉你两个非负整数 a 和 b。找到满足 X*a Y*b 1 的非负整数 X 和整数 Y。如果没有这样的答案#xff0c;请写 “sorry”。
思路#xff1a;这是一道扩展欧几里得模板题#xff0c;唯一容易错的就是 x 有可能是负数#xff0c;要把它改成非负数… 题目大意现在告诉你两个非负整数 a 和 b。找到满足 X*a Y*b 1 的非负整数 X 和整数 Y。如果没有这样的答案请写 “sorry”。
思路这是一道扩展欧几里得模板题唯一容易错的就是 x 有可能是负数要把它改成非负数。
a*xb*ygcd(a,b)1成立所以 a*(xb)b(y-a)1 仍成立。
所以 x (xb)%b , y(1-a*x)/b。
代码如下
#includebits/stdc.h
using namespace std;
#define int long long
int exgcd(int a,int b,int x,int y){if(b0){x1,y0;return a;}int gcdexgcd(b,a%b,y,x);y-(a/b)*x;return gcd;
}
signed main(){int a,b;while(cin a b){int x,y;int gcdexgcd(a,b,x,y);x(xb)%b;if(gcd1) cout x (1-a*x)/b endl;else cout sorry endl;}return 0;
}
