51nod 1256 乘法逆元

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/48871349

题目链接： [

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1256
](http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1256)

水题求逆元。。

代码：

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <vector>

using namespace std;

long long ext_gcd(long long a, long long b, long long &x, long long &y)
{
    if (a == 0 && b == 0) return -1;
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    long long d = ext_gcd(b, a%b, y, x);
    y -= a / b*x;
    return d;
}

//求逆元素
// ax=1(mod n)
long long mod_reverse(long long a, long long n)
{
    long long x, y;
    long long d = ext_gcd(a, n, x, y);
    if (d == 1)
        return (x%n + n) % n;
    else
        return -1;
}

int main()
{
    long long a, b;
    while (cin >> a >> b)
    {
        int ans = mod_reverse(a, b);
        cout << ans << endl;
    }
    return 0;
}