#P1078. 【模板】扩展欧几里得(不定方程)

    ID: 90 传统题 1000ms 256MiB 尝试: 0 已通过: 0难度: 普及+/提高− ← 上一题 下一题 → 随机一题 上传者: 标签 模板题 扩展欧几里得 数论 不定方程
显示设置

【模板】扩展欧几里得(不定方程)

题目描述

给出 qq 组正整数 a,ba,b,求关于 x,yx,y 的方程

ax+by=gcd⁡(a,b)ax+by=\gcd(a,b)

的一组整数解 (x,y)(x,y)。

输入格式

第一行一个整数 qq。

接下来 qq 行,每行两个正整数 a,ba,b。

输出格式

输出 qq 行,每行两个整数 x,yx,y。

如果有多组解,输出任意一组即可。

输入输出样例 #1

输入 #1

2
3 5
4 6

输出 #1

2 -1
-1 1

说明

数据范围

  • 对于 100%100\% 的数据,1≤q≤1051\le q\le 10^5,1≤a,b≤2×1091\le a,b\le 2\times10^9。