51nod:1256 乘法逆元

51nod:1256 乘法逆元

Input

输入2个数M, N中间用空格分隔（1 <= M < N <= 10^9)

Output

输出一个数K，满足0 < K < N且K * M % N = 1，如果有多个满足条件的，输出最小的。

Input示例

2 3

Output示例

2

在欧几里得（GCD）算法中，我们可以求得两个数的最大公因数，也就是辗转相除法啦！

而在扩展欧几里得算法中有说明，对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在无数组整数对 x，y ，使得 gcd（a，b）=ax+by。

对于 K * M % N = 1, 其实这个式子是可以化为 K * M - T * N = 1；  这就和 a * x + b * y + c = 0 一样的， 又因题目讲明 gcd （M ， N） = 1；  所以可以直接上扩展欧几里得了， 得出的 K 可能是负数， 要注意处理一下。

AC代码：

#includeusing namespace std;int exgcd(int m,int n,int &x,int &y) //扩展GCD{ if(n==0) { x=1; y=0; return m; } int r=exgcd(n,m%n,x,y); int t=x; x=y; y=t-(m/n)*y; return r;}int main(){ int n,m,x,y; cin>>m>>n; exgcd(m,n,x,y); cout<<(x%n+n)%n<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。