卢卡斯定理求组合数
作者:
amagi
,
2023-07-30 17:30:18
,
所有人可见
,
阅读 127
#include <iostream>
#define ll long long
using namespace std;
ll qim(ll a,ll b,ll c){
ll res = 1;
while(b){
if(b & 1) res = res * a % c;
a = a * a % c;
b >>= 1;
}
return res;
}
ll C(ll a,ll b,ll c){
if(b > a) return 0;
ll res = 1;
for(int i = 1,j = a; i <= b; i ++,j --){
res = res * j % c;
res = res * qim(i,c - 2,c) % c;
}
return res;
}
ll luks(ll a,ll b,ll c){
if(a < c && b < c) return C(a,b,c);
else
return C(a % c,b % c,c) * luks(a / c,b / c,c) % c;
}
void solve(){
ll a,b,c;
cin >> a >> b >> c;
cout << luks(a,b,c) << endl;
return ;
}
int main(){
ll t;
cin >> t;
while(t --)
solve();
return 0;
}