组合数 III,快速幂只需计算一次,极大节省时间 (100ms内)
#include <iostream>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int qmi(int a,int b,int p)
{
LL res=1%p;//能正确处理当p = 1, b = 0的情况,最终res是0。(此题p是质数,可直接res=1)
while(b) //只要b还不为0,每次取b的二进制表示最低位的1计算
{
if(b&1) res=res*a % p;//按公式计算
a=(LL)a*a % p; //防止两个int相乘爆int
b >>= 1; //b右移一位
}
return res;
}
int C(int a,int b,int p) //公式法计算c(a,b) = a(a-1)(a-2)···(a-b+1)/b!
{
if(b>a) return 0;
LL x=1,y=1;
for(int i=a,j=1;j<=b;i--,j++)
{
x=x*i % p;
y=y*j % p; //分别计算分子和分母.(其实i+j=a+1,i和j可以合并成一个变量)
}
return x*qmi(y,p-2,p) % p;
}
int lucas(LL a,LL b,int p) //lucas定理: c(a,b) mod p=c(a%p,b%p)*c(a/p,b/p) mod p
{
if(a<p && b<p) return C(a,b,p); //当a,b足够小即可按公式直接计算
return (LL)C(a%p,b%p,p)*lucas(a/p,b/p,p) % p; //按照卢卡斯定理递推计算
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
LL a,b,p;
scanf("%lld%lld%lld",&a,&b,&p);
printf("%d\n",lucas(a,b,p));
}
return 0;
}