同余逆元费马小定理

　　　如果会数学就好了　　　　

前言

菜鸡不会打【P7108】，来补数学知识

给定一个正整数$m$，如果两个整数$a$和$b$满足$a-b$能够被$m$整除，即$(a-b)/m$得到一个整数，那么就称整数$a$与$b$对模$m$同余，记作 $a≡b(\mod m)$ 。

对模$m$同余是整数的一个等价关系。

如果$p$是一个质数，而整数$a$不是$p$的倍数，则有 $a^{p-1}≡1（mod p）$ 。

$1\%p=a^{p-1}\%p \\ => \frac 1 a \% p = a^{p-2}\%p$

因此，在计算$\frac{b^h-1}{b-1}$时，我们可以将其转化成$(b^h-1)*inverse(b-1)$计算。

long long invEl(int x)
{
    return qpow(x, M - 2, M);
}

【黑人问号脸.jpeg】