#A3500. 扩展欧几里得算法

扩展欧几里得算法

题目描述

输入两个整数a,ba,b,求一组x,yx,y

使得a×x+b×y=gcd(a,b)a \times x +b \times y=gcd(a,b)

输入

第一行输入两个整数a,ba,b

输出

输出满足条件的两个整数x,yx,y

4 6
-1 1

提示

如果有多组x,yx,y,输出任意满足的x,yx,y即可.

1a,b2×1091 \leq a,b \leq 2 \times 10^9