本文共 1192 字，大约阅读时间需要 3 分钟。

题目链接:

题目描述

给定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);

Accepted Code:

/*  * @Author: lzyws739307453  * @Language: C++  */#include 
   
    using 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;}
   

转载地址：https://lzyws739307453.blog.csdn.net/article/details/99693180 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！