扩展欧几里得 题目描述 给定 n 对正整数 ai,bi，对于每对数，求出一组 xi,yi，使其满足 ai×xi+bi×yi=gcd(ai,bi)。 输入 第一行包含整数 n。 接下来 n 行，每行

扩展欧几里得

题目描述

Kl8100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
给定 n 对正整数 ai,bi，对于每对数，求出一组 xi,yi，使其满足 ai×xi+bi×yi=gcd(ai,bi)。

输入

Kl8100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第一行包含整数 n。Kl8100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
接下来 n 行，每行包含两个整数 ai,bi。

输出

Kl8100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出共 n 行，对于每组 ai,bi，求出一组满足条件的 xi,yi，每组结果占一行。Kl8100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
本题答案不唯一，输出任意满足条件的 xi,yi 均可。

样例输入

2
4 6
8 18

样例输出

-1 1
-2 1

提示

Kl8100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1≤n≤10^5,Kl8100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1≤ai,bi≤2×10^9