767. 扩展欧几里得算法
SPJ
时间限制：1500 MS 内存限制：128 MB
题目描述
# 扩展欧几里得算法 ## 题目描述 给定 $n$ 对正整数 $a_i,b_i$。对于每对数，求出一组整数 $x_i,y_i$，使其满足： $$ a_i x_i+b_i y_i=\gcd(a_i,b_i) $$ 其中，$\gcd(a_i,b_i)$ 表示 $a_i$ 与 $b_i$ 的最大公约数。 ## 输入格式 从文件 `exgcd.in` 中读入数据。 第一行包含一个整数 $n$，表示正整数对的数量。 接下来 $n$ 行，每行包含两个正整数 $a_i,b_i$。 ## 输出格式 将结果输出到文件 `exgcd.out` 中。 输出共 $n$ 行。第 $i$ 行包含两个整数 $x_i,y_i$，满足： $$ a_i x_i+b_i y_i=\gcd(a_i,b_i) $$ **本题答案不唯一，输出任意满足条件的整数解均可。** $x_i,y_i$ 可以为负数。 ## 数据范围 - $1 \le n \le 10^5$。 - $1 \le a_i,b_i \le 2 \times 10^9$。 ## 样例输入 ``` 2 4 6 8 18 ``` ## 样例输出 ``` -1 1 -2 1 ``` ## 样例说明 对于第一组数据，$4\times(-1)+6\times1=2=\gcd(4,6)$。 对于第二组数据，$8\times(-2)+18\times1=2=\gcd(8,18)$。 ## 时间与空间限制 - 时间限制：$1500$ 毫秒。 - 内存限制：$128$ MB。