乘法逆元

前置

快速幂

递归版

// a 的 b 次方在模 p 意义下的结果
int quick_pow(int a, int b, int p)
{
    if (b == 0)
        return 1;
    int x = quick_pow(a, b / 2, p);
    if (b % 2 == 0)
        return x * x % p;
    return x * x % p * a % p;
}

非递归版

// a 的 b 次方在模 p 意义下的结果
int quick_pow(int a, int b, int p)
{
    int res = 1;
    while (b > 0)
    {
        if (b % 2 == 1)
            res = res * a % p;
        b /= 2;
        a = a * a % p;
    }
    return res;
}

费马小定理求逆元

// a 在模 p（质数） 意义下的逆元
int inv(int a, int p)
{
    return quick_pow(a, p - 2, p);
}