zcmimi's blog

Lucas定理

C_n^m\pmod p\equiv C_{n\mod p}^{m\mod p}*C_{\lfloor n/p\rfloor}^{\lfloor m/p\rfloor}\pmod p

就是一个组合数可以拆成P进制下的乘积

这个算法可以处理当m,n非常大的时候的取模

扩展:仅当(n\&m)=m时,C(n,m) \equiv 1 \bmod 2

裴蜀定理

ax+by=c(x\in Z^*,y\in Z^*)\Leftrightarrow\gcd(a,b)|c

欧拉定理

\gcd(a,p)=1(互质),那么a^{\varphi(p)} \equiv 1 \pmod p

费马小定理(欧拉定理特例)

对于质数p,任意整数a,均满足: a^p \equiv a \pmod p

欧拉定理的推论

\gcd(a,p)=1,那么对于任意正整数b,有:

a^b \equiv a^{b \mod \varphi(p)} \bmod n

扩展欧拉定理

b\ge \varphi(m)时,a^b \equiv a^{(b \mod \varphi(m))+\varphi(m)} \pmod m

卡特兰数

1,1,2,5,14,42,132,429,1430,4862,...(从第0项开始)

f_1=1 \\ f_n=\sum_{i=1}^{n-1}f_if_{n-i-1} \\ f_n=\frac{1}{n+1}{2n\choose n} \\ f_{n+1}=\frac{4n+2}{n+2}f_n

数论定理
comment评论
Search
search