lucas学习笔记
小蒟蒻的第一篇学术文章，对lucas理解不够透彻，如有错误，望指正，同时望支持
注：下文定义\(\binom{a}{b}\)为\(\frac {b!} {a!(b-a)!}\quad\) (即组合数）
定理内容：
p为质数，则有
\(\binom{n}{m}\equiv\binom{n\mod\ p}{m\mod\ p}\times \binom{\frac{n}{p}}{\frac{m}{p}}\ (mod\ \ p)\)
常用于在\(m>p,n>p\) 时求 \(\binom{n}{m}\mod\ p\)
先证明两个引理：
引理1(后面用来证明引理2)：
有\(p\)为质数，又有\(1\le k \le p-1\)
则有\(p\mid\binom{k}{p}\)
证明:
\(\binom{k}{p}=\frac {p} {k}\times\binom{k-1}{p-1}\)
(这里不能只提取一个\(p\)而不是\(\frac {p} {k}\)，\(\frac {(p-1)!}{k!(p-k)!}\)不是组合数!)
移项得:
\(k\times\binom{k}{p}=p\times\binom{k-1}{p-1}\)
所以\(p\mid k\times\binom{k}{p}\)
因为\(p\)为素数
所以\(p\nmid k\) , \(p\mid\binom{k}{p}\)
引理1证毕
引理2：
\((x+y)^p\equiv x^p+y^p\ (mod\ \ p)\)
同理：\((x+y)^{p^k}\equiv x^{p^k}+y^{p^k}\ (mod\ \ p)\)
证明:
\((x+y)^p=x^p+\sum_{k=1}^{p-1}\binom{k}{p}x^ky^{p-k}+y^p\)
由引理1知:\(p\mid\binom{k}{p}\)
所以\((x+y)^p\equiv x^p+y^p\ (mod\ \ p)\)
同理转化可得\((x+y)^{p^k}\equiv x^{p^k}+y^{p^k}\ (mod\ \ p)\)也成立
引理2证毕
正式开始证明：
先将m转换p进制：\(m=a_0+a_1p+a_2p^2+...+a_kp^k\)
则有
\((1+x)^m=(1+x)^{a_0+a_1p+a_2p^2+...+a_kp^k}\)
\(\qquad\qquad=(1+x)^{a_0}(1+x)^{a_1p}(1+x)^{a_2p^2}...(1+x)^{a_kp^k}\)
引用引理2：
\((1+x)^m\equiv(1+x)^{a_0}(1+x^{p})^{a_1}(1+x^{p^2})^{a_2}...(1+x^{p^k})^{a_k}\ (mod\ \ p)\)
引用二项式定理：
\((1+x)^m\equiv(\sum_{j=0}^{a_0}\binom{j}{a0}x^j)(\sum_{j=0}^{a_1}\binom{j}{a_1}x^{pj})(\sum_{j=0}^{a_2}\binom{j}{a_2}x^{p^2j})...(\sum_{j=0}^{a_k}\binom{j}{a_k}x^{p^kj})\ (mod\ \ p)\)
讨论等式两边\(x^n\)的系数
左边：\(\binom{n}{m}\)
右边：
我们看到x的排列形式为进制展开的形式
而n可转换为\(b_0+b_1p+b_2p^2+...+b_kp^k\)
所以当式子的j依次取\(b_0,b_1,b_2...b_k\)时，可以形成
\(x^n\),\(x^n\)有且只有一个
(即当j满足上述条件后，只出现这一次)
此时右边\(x^n\)的系数为：\(\binom{b0}{a0}\binom{b1}{a1}\binom{b2}{a2}...\binom{bk}{ak}\)
所以\(\binom{n}{m}\equiv\binom{b0}{a0}\binom{b1}{a1}\binom{b2}{a2}...\binom{bk}{ak}\ (mod\ \ p)\)
根据开头\(m\)的分解，我们知道
\(a_0=a\mod\ p \quad b_0=b\mod\ p\)
\(a_1=\frac{a}{p}\mod\ p \quad b_1=\frac{b}{p}\mod\ p\)
\(a_2=\frac{a}{p^2}\mod\ p \quad b_2=\frac{b}{p^2}\mod\ p\)
...
\(a_k=\frac{a}{p^k}\mod\ p \quad b_k=\frac{b}{p^k}\mod\ p\)
所以写成函数递归，就是：
\(lucas(m,n)\equiv \binom{n\mod\ p}{m\mod\ p}\times lucas(\frac{m}{p},\frac{n}{p})\ (mod\ \ p)\)
到此，证毕
献上模板Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
int N,m,n,p;
int qmi(int a,int b)
{
int ret=1;
while(b)
{
if(b&1) ret=ret*a%p;
a=a*a%p;
b>>=1;
}
return ret;
}//快速幂求逆元
int C(int m,int n)
{
int res=1;
for(int i=1,j=m;i<=n;i++,j--)
{
res=res*j%p;
res=res*qmi(i,p-2)%p;//除以i等于乘逆元
}
return res;
}
/*求组合数这里可以用阶乘预处理等优化
这里用朴素求法，有些题会被卡时间
建议以后这里直接优化 */
int lucas(int m,int n)
{
if(m<p&&n<p) return C(m,n);
return C(m%p,n%p)*lucas(m/p,n/p)%p;
}//核心代码！
signed main()
{
scanf("%lld",&N);
while(N--)
{
scanf("%lld%lld%lld",&m,&n,&p);
printf("%lld\n",lucas(m,n));
}
return 0;
}
没有人有耐心能看到这里吧