20024 - 拓展欧几里得算法求逆元
时间限制 : 1 秒
内存限制 : 128 MB
扩展欧几里得算法用于求解 二元一次不定方程：
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题目条件不同）。求n在模p下的逆元
输入
一行，两个数字，分别表示n和p
输出
n在模p下的逆元
样例
输入
4 7
输出
2
提示
0 < n < p < 2^{31} 。p和n互质