求逆元

ACM模版

扩展欧几里得法

参考：《GCD》

/* * 扩展欧几里得法（求ax + by = gcd） */
// 返回d = gcd(a, b);和对应于等式ax + by = d中的x、y
long long extendGcd(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 = extendGcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

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

简洁写法

/* * 简洁写法I * 只能求a < m的情况，且a与m互质 * 求ax = 1(mod m)的x值，即逆元(0 < a < m) */
long long inv(long long a, long long m)
{
    if (a == 1)
    {
        return 1;
    }
    return inv(m % a, m) * (m - m / a) % m;
}

欧拉函数法

/* * 欧拉函数法 * a 和 m 互质 */
// 快速幂取模
long long powM(long long a, long long b, long long m)
{
    long long tmp = 1;
    if (b == 0)
    {
        return 1;
    }
    if (b == 1)
    {
        return a % m;
    }

    tmp = powM(a, b >> 1, m);
    tmp = tmp * tmp % m;

    if (b & 1)
    {
        tmp = tmp * a % m;
    }

    return tmp;
}

long long inv(long long a, long long m)
{
    return powM(a, m - 2, m);
}

2018.6.1 修改 tmp=powM(a,b>>1,m); t m p = p o w M ( a , b >> 1 , m ) ; 感谢评论区大佬的提醒。

欧拉函数法（求阶乘逆元）

typedef long long ll;

const ll MOD = 1e9 + 7;     // 必须为质数才管用
const ll MAXN = 1e5 + 3;

ll fac[MAXN];       // 阶乘
ll inv[MAXN];       // 阶乘的逆元

ll QPow(ll x, ll n)
{
    ll ret = 1;
    ll tmp = x % MOD;

    while (n)
    {
        if (n & 1)
        {
            ret = (ret * tmp) % MOD;
        }
        tmp = tmp * tmp % MOD;
        n >>= 1;
    }

    return ret;
}

void init()
{
    fac[0] = 1;
    for (int i = 1; i < MAXN; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
    }
    inv[MAXN - 1] = QPow(fac[MAXN - 1], MOD - 2);
    for (int i = MAXN - 2; i >= 0; i--)
    {
        inv[i] = inv[i + 1] * (i + 1) % MOD;
    }
}

                                PS:2016.12.14添加