4368 扩展欧几里得算法
时间限制2 S
内存限制128 MB
通过率56%(89 / 159)
题目描述
给定 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
来源