组合数函数的优化,大概快个十倍,题解区和y总的太慢
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 100010, mod = 1e9+7;
int fact[N], infact[N];
int qmi(int a, int k, int p)
{
int res = 1;
while(k)
{
if(k & 1)
res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
int C(int a, int b, int p)
{
if(a < b)
return 0;
int down = 1, up = 1;
for(int i=a, j=1; j<=b; i--, j++)
{
up = (LL)up * i % p;
down = (LL)down * j % p;
}
return (LL)up * qmi(down, p-2, p) % p;
}
int lucas(LL a, LL b, int p)
{
if(a<p && b<p)
return C(a, b, p);
else
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;
cin>>a>>b;
cin>>p;
cout<<lucas(a, b, p)<<endl;
}
return 0;
}