如果会数学就好了
前言
菜鸡不会打【P7108】,来补数学知识
同余
给定一个正整数$m$,如果两个整数$a$和$b$满足$a-b$能够被$m$整除,即$(a-b)/m$得到一个整数,那么就称整数$a$与$b$对模$m$同余,记作。
对模$m$同余是整数的一个等价关系。
费马小定理
如果$p$是一个质数,而整数$a$不是$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】