本文共 1192 字,大约阅读时间需要 3 分钟。
题目链接:
时/空限制:1.500000s / 64MB给定n对正整数ai,bi,对于每对数,求出一组xi,yi,使其满足ai∗xi+bi∗yi=gcd(ai,bi)。
第一行包含整数n。
接下来n行,每行包含两个整数ai,bi。
输出共n行,对于每组ai,bi,求出一组满足条件的xi,yi,每组结果占一行。
本题答案不唯一,输出任意满足条件的xi,yi均可。
1≤n≤10^5,
1≤ai,bi≤2∗10^9
2
4 6 8 18
-1 1
-2 1
题意:求出一组x,y,使其满足a∗x+b∗y=gcd(a,b)。
思路:利用扩展欧几里得算法:设ax1+by1=gcd(a,b), bx2+(a%b)y2=gcd(b,a%b);
由gcd(a,b)=gcd(b,a%b),可得: ax1+by1=bx2+(a%b)y2; 即:ax1+by1=bx2+(a-(a/b)*b)y2 =ay2+bx2-(a/b)*by2; 即:ax1+by1=ay2 + b(x2-(a/b)*y2) 根据恒等定理,对应项相等,得:x1=y2; y1=x2-(a/b)*y2; 这样我们就得到了:x1,y1的值基于x2,y2,所以我们可以通过递归求解。Accepted Code:
/* * @Author: lzyws739307453 * @Language: C++ */#includeusing namespace std;const int MAXN = 1e6 + 5;//写法一void Exgcd_1(int a, int b, int &x, int &y) { if (!b) x = 1, y = 0; else { Exgcd_1(b, a % b, x, y); int t = x; x = y; y = t - a / b * y; }}//写法二void Exgcd_2(int a, int b, int &x, int &y) { if (!b) x = 1, y = 0; else Exgcd_2(b, a % b, y, x), y -= a / b * x;}int main() { int t; scanf("%d", &t); while (t--) { int a, b, x, y; scanf("%d%d", &a, &b); Exgcd_2(a, b, x, y); printf("%d %d\n", x, y); } return 0;}
转载地址:http://mubtf.baihongyu.com/