51Nod 1256:乘法逆元

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#problemId=1256¬iceId=335717

求M模N的乘法逆元，且gcd(M,N) = 1，即M和N互质，则用扩展欧几里得求乘法逆元

AC代码：

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int x,y;
int extgcd(int a, int b,int &x,int &y)
{
    int d = a;
    if(b != 0)
    {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }
    else
    {
        x = 1;
        y = 0;
    }
    return d;
}
int mod_inverse(int b, int n)
{
    int x, y;
    extgcd(b, n, x, y);
    return (n + x % n) % n;
}

int main()
{
    int M,N;
    while(~scanf("%d%d",&M,&N))
    {
        printf("%d\n",mod_inverse(M,N));
    }
    return 0;
}