Module: 扩展欧几里得算法


Problem

2 /2


丢番图方程

Problem

给出自然数 abc。如果方程 \(ax+by=c\) 有整数解,则选择数 x 具有最小的非负值并输出此解(两个数 x 和 y 分隔 一个空格).如果没有解决方案,则打印单词 Impossible

输入 
输入三个自然数。

印记
打印问题的答案。

注意
算法的复杂度必须等于欧氏算法的复杂度+一个常数。
 
例子
<头> <日># <正文>
输入 输出
1 1 2 3 1 1
2 10 6 8 2 -2