乘法逆元(分数取模)

费马小定理

费马小定理如下:$ a^{p-1}\equiv 1(mod\ p) $ 注意p要为质数

同样我们可以稍作变换:$a * a^{p-2}\equiv 1(mod\ p)$ 很明显可以看出,$a^{p-2}$就是$a$的逆元

而计算方法就是用快速幂来做,代码如下:

1
2
3
4
5
6
7
8
9
10
11
long long power(long long x, long long y, long long mod)
{
long long r = 1;
while ( y )
{
if ( y & 1 ) r = r * x % mod;
x = x * x % mod;
y >>= 1;
}
return r;
}

分数取模

我们要计算分数的模,如下:$\frac{x}{y}\equiv x*y^{-1}(mod\ p)$

化简后为:$\frac{x}{y}\equiv x^{y^{mod-2}}(mod\ p)$

代码也就可以这样计算:

1
ans = power(power(x, y, mod), mod-2, mod);

备注:本文所有代码经过huhao大佬的修改