查看“︁乘法逆元”︁的源代码

==前置==

===快速幂===

====递归版====

<syntaxhighlight lang="cpp" line>
// 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;
}
</syntaxhighlight>

====非递归版====

<syntaxhighlight lang="cpp" line>
// 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;
}
</syntaxhighlight>

==费马小定理求逆元==

<syntaxhighlight lang="cpp" line>
// a 在模 p（质数） 意义下的逆元
int inv(int a, int p)
{
    return quick_pow(a, p - 2, p);
}
</syntaxhighlight>