问题 L: 扩展欧几里得算法
内存限制：128 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：Special Judge
上传者：
提交：149
通过：80
题目描述
给定 n 对正整数 ai , bi，对于每对数，求出一组 xi , yi，使其满足 ai × xi + bi × yi = gcd(ai, bi)。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含两个整数 ai , bi 。
输出格式
输出共 n 行，对于每组 ai , bi ，求出一组满足条件的 xi , yi,每组结果占一行。
本题答案不唯一，输出任意满足条件的 xi , yi均可。
输入样例 复制
2
4 6
8 18输出样例 复制
-1 1
-2 1数据范围与提示
1 ≤ n ≤ 105,
1 ≤ ai , bi ≤2×109
1 ≤ ai , bi ≤2×109