扩展欧几里得算法用于求解 **二元一次不定方程**：

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

其中 $a, b$ 是已知整数，$x, y$ 是整数解。
$ \gcd(a, b) = \gcd(b, a \bmod b) $ 在辗转相除的过程中，**反向递推**得到 $ x $ 和 $ y $。
当$gcd（a,b）=1$的时候即退化成求逆元的形式，给定一个数n和模数p，其中p和n互素（这与oj上的[14104](https://old.ynoip.cn/p/14104 "14104")题目条件不同）。求n在模p下的逆元

一行，两个数字，分别表示n和p

n在模p下的逆元

$0 < n < p < 2^{31} $。p和n互质