G27 求组合数 卢卡斯定理

#include<bits/stdc++.h> 
using namespace std; 
typedef long long LL; 
const int N=1e6+10;
LL P, fac[N]; 
LL qpow(LL a, LL b)  
{
	LL res=1%P;a%=P;
	for(;b;b>>=1,a=a*a%P)if(b&1)res=res*a%P;
	return res;
}  
LL C(LL n, LL m)  
{
	return (n<m) ? 0ll :fac[n]*qpow(fac[m], P-2)%P*qpow(fac[n-m], P-2)%P;  
}  
LL Lucas(LL n, LL m)  
{
	return (m==0) ? 1ll : C(n%P, m%P)*Lucas(n/P, m/P)%P;  
}  
int main()  
{
	int T;cin>>T;
	while(T--)
	{
		LL n, m;cin>>n>>m>>P;
		fac[0]=1;for(int i=1;i<=P;i++)fac[i]=fac[i-1]*i%P; 
		cout<<Lucas(n, m)<<"\n";
	}
	return 0;  
}

G27 求组合数 卢卡斯定理

#include<bits/stdc++.h> 
using namespace std; 
typedef long long LL; 
const int N=1e6+10;
LL P,fac[N]; 
LL qpow(LL a,LL b)  
{
	LL res=1%P;a%=P;
	for(;b;b>>=1,a=a*a%P)if(b&1)res=res*a%P;
	return res;
}  
LL C(LL n,LL m)  
{
	return (n<m) ? 0ll :fac[n]*qpow(fac[m],P-2)%P*qpow(fac[n-m],P-2)%P;  
}  
LL Lucas(LL n,LL m)  
{
	return (m==0) ? 1ll : C(n%P,m%P)*Lucas(n/P,m/P)%P;  
}  
int main()  
{
	int T;cin>>T;
	while(T--)
	{
		LL n,m;cin>>n>>m>>P;
		fac[0]=1;for(int i=1;i<=P;i++)fac[i]=fac[i-1]*i%P; 
		cout<<Lucas(n,m)<<"\n";
	}
	return 0;  
}