数学（杂记）

逆元

逆元满足： $a\ast inv\left(a\right)\equiv 1(mod$a∗inv(a)≡1(mod $p)$p)

1.模 $p$p为素数的逆元

利用费马小定律: $a^{p-1}\equiv 1(mod$ap−1≡1(mod $p)$p)
则 $inv\left(a\right)=a^{p-2}$inv(a)=ap−2

2.不要求模 $p$p为质数的逆元求法

利用拓展欧几里得算法，既可以求合数模，也可以求素数模；并且常数较小，实际速度比快速幂更好一点，但快速幂好写一些。

给定模数 $m$m，求 $a$a的逆相当于求解 $ax=1(mod$ax=1(mod $m)$m)
这个方程可以转化为 $ax-my=1$ax−my=1
然后套用求二元一次方程的方法，用扩展欧几里得算法求得一组 $x0,y0$x0,y0和 $gcd$gcd
检查 $gcd$gcd是否为1
$gcd$gcd不为1则说明逆元不存在
若为 $1$1，则调整 $x0$x0到 $0$0~ $m-1$m−1的范围中即可

void exgcd(int a,int b,int &d,int &x,int &y){
    if (!b) d=a, x=1, y=0;
    else exgcd(b,a%b,d,y,x), y-=a/b*x;
}

ll inv(int a, int mod) {
    ll ret, d, y;
    exgcd(a,mod,d,ret,y);
    return d==1?(ret+mod)%mod:-1;
}

3.递归求逆元

递推公式： $inv\left[1\right]=1$inv[1]=1, $inv\left[i\right]=(mod-mod/i)\ast inv[mod$inv[i]=(mod−mod/i)∗inv[mod% $i]$i]% $mod;$mod;

inv[1]=1;
for(int i=2; i<mod; ++i) inv[i]=(mod-mod/i)*inv[mod%i]%mod;

也可用于单次求逆元（但一般不用）

ll inv(ll a, ll m) { return a==1?1:(m-m/a)*inv(m%a,m)%m; }

4.利用递归预处理阶乘的逆元

inv[0]=inv[1]=1;
for(int i=2; i<mod; ++i) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(int i=2; i<mod; ++i) inv[i]=inv[i]*inv[i-1]%mod;