扩展Lucas定理 扩展Lucas板子

题意概述：多组询问，给出N,K,M，要求回答C(N,K)%M，1<=N<=10^18,1<=K<=N,2<=M<=10^6

分析：

　　模数不为质数只能用扩展Lucas，裸题没什么好说的。

　　emmmmmm......知识点我就不讲了吧......（主要是我现在都还没有参透博客园怎么放公式）直接丢代码！加上了一些棒棒的优化~

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<set>

 #include<map>

 #include<vector>

 #include<cctype>

 using namespace std;

 typedef long long LL;

 const int maxn=;

 LL N,K; int M;

 int pri[maxn],tot; bool ntp[maxn];

 void get_pri(){

     ntp[]=ntp[]=;

     for(int i=;i<=;i++){

         if(!ntp[i]) pri[++tot]=i;

         for(int j=;j<=tot&&1ll*pri[j]*i<=;j++){

             ntp[pri[j]*i]=;

             if(i%pri[j]==) break;

         }

     }

 }

 void exgcd(int a,int b,LL &d,LL &x,LL &y){

     if(!b) d=a,x=,y=;

     else exgcd(b,a%b,d,y,x),y-=a/b*x;

 }

 int inv(int a,int p){

     LL d,x,y; exgcd(a,p,d,x,y);

     return (x%p+p)%p;

 }

 int qkpow(int x,LL y,int p){

     int re=,t=x;

     for(int i=;(1ll<<i)<=y;i++){

         if((1ll<<i)&y) re=1ll*re*t%p;

         t=1ll*t*t%p;

     }

     return re;

 }

 int J(LL n,int p,int pt,int mul){

     if(n<=) return ;

     int re=;

     if(n>=pt) re=qkpow(mul,n/pt,pt);

     for(int i=;i<=n%pt;i++)

         if(i%p) re=1ll*re*i%pt;

     return 1ll*re*J(n/p,p,pt,mul)%pt;

 }

 int C(LL n,LL m,int p,int pt){

     LL k=,t;

     for(t=n;t;t/=p) k+=t/p;

     for(t=m;t;t/=p) k-=t/p;

     for(t=n-m;t;t/=p) k-=t/p;

     int pw=qkpow(p,k,pt); if(!pw) return ;

     int mul=;

     for(int i=;i<pt;i++)

         if(i%p) mul=1ll*mul*i%pt;

     int a=J(n,p,pt,mul),b=inv(J(m,p,pt,mul),pt),c=inv(J(n-m,p,pt,mul),pt);

     return 1ll*pw*a%pt*b%pt*c%pt;

 }

 int exLucas(LL n,LL m,int p){

     int re=,t=p;

     for(int i=;i<=tot&&pri[i]<=t;i++){

         if(t%pri[i]) continue;

         int pt=,c;

         while(t%pri[i]==) pt*=pri[i],t/=pri[i];

         c=C(n,m,pri[i],pt);

         re=(re+1ll*p/pt*c%p*inv(p/pt,pt)%p)%p;

     }

     return re;

 }

 int main()

 {

     get_pri();

     while(cin>>N>>K>>M) cout<<exLucas(N,K,M)<<'\n';

     return ;

 }