加载中...

   如果会数学就好了    

前言

菜鸡不会打【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】

Reference