504027 - 扩展欧几里得算法

【题目描述】扩展欧几里得算法(ExGCD)

扩展欧几里得算法的定义是:设非负整数a,b不全为0,则一定存在整数x和y,使得gcd(a,b)=ax+by。例如a=3,b=7,gcd(3,7)=1,有x=-2,y=1,即-2×3+1×7=gcd(3,7)=1。简言之,在求得a,b的最大公约数的同时,还能求出一组解x,y。

输入

有多组数据,每组数据输入两个整数即a和b。

输出

输出x和y的解,使gcd(a,b)=ax+by,具体格式见输出样例。

样例

输入

16 12
12 16

输出

16*1+12*-1=4
12*-1+16*1=4
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题