数论--求逆元

模板：

#include<bits/stdc++.h>
using namespace std;
//求a在mod m的情况下的逆元  

// 1.扩展欧几里得法
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;
}
long long inv1(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;  //  无逆元
    }
}


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

/*
    3.欧拉函数法 
    a和m互质 m为素数 
    快速幂取模 
*/
long long powM(long long a, long long b, long long m)
{
    long long t=1,tt=a%m;
    while(b)
    {
        if(b&1)t=t*tt%m;
        tt=tt*tt%m;
        b>>=1;
    }
    return t;
}

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


//4.补充 求阶乘的逆元
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;
    }
} 


int main()
{
    long long a,m;
    init(); 
//    cin>>a>>m;
//    cout<<inv1(a,m)<<endl;
//    cout<<inv2(a,m)<<endl;
//    cout<<inv3(a,m)<<endl;
    for(int i=1;i<=5;i++)
    {
        cout<<fac[i]<<" "<<inv[i]<<endl;
    }
    return 0;
 }