题目链接 原题链接
我遇到了如下问题。
错误的代码：
#include<bits/stdc++.h>
using namespace std;
long long qmi(long long a,long long b,long long p)
{
long long res=1%p;
while(b)
{
if(b&1)res=res*a%p;
a=a*a%p;
b>>=1;
}
return res;
}
long long C(long long a,long long b,long long p)
{
if(a<b)return 0;
int res=1,cnt=1;
while(b+b>a)
{
b=a-b;
}
for(int i=1,j=a-b+1;i<=b;i++,j++)
{
res=res*j%p;
cnt*=i%p;
}
return res*qmi(cnt,p-2,p)%p;
}
long long lucas(long long a,long long b,long long p)
{
if(a<p&&b<p)return C(a,b,p);
return C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
long long x,y,z;
scanf("%lld %lld %lld",&y,&x,&z);
printf("%lld\n",lucas(y,x,z));
}
return 0;
}
样例正确，但却WA一片
