887. 求组合数 III (卢卡斯定理)
作者:
闪回
,
2024-03-17 21:07:10
,
所有人可见
,
阅读 12
#include<bits/stdc++.h>
using namespace std;
#define int long long
int qmi(int a,int b,int p)
{
int res = 1;
while(b)
{
if(b & 1)res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
int C(int a,int b,int p)
{
int res = 1;
for(int i = 1,j = a;i<=b;i++,j--)
{
res = res * j % p;
res = res * qmi(i,p-2,p) % p;
}
return res;
}
int lucas(int a,int b,int p)
{
if(a<p && b<p)return C(a,b,p);
else return C(a%p,b%p,p) * lucas(a/p,b/p,p) % p;
}
signed main()
{
int n;
cin>>n;
while(n--)
{
int a,b,p;
cin>>a>>b>>p;
cout<<lucas(a,b,p)<<endl;
}
return 0;
}