int ans=0;
long long rec=p;
while(x>=rec)
{
ans+=x/rec;
rec*=p;
}
return ans;
}
//计算n的k次方对m取模，二分法
int pow(long long n,int k,int M)
{
long long ans=1;
while(k)
{
if(k&1)
{
ans=(ans*n)%M;
}
n=(n*n)%M;
k>>=1;
}
return ans;
}
//计算C（n，m）
int combination(int n,int m)
{
const int M=10007;
vector
long long ans=1;
int num;
for(int i=0;i
num=cal(n,prim[i])-cal(m,prim[i])-cal(n-m,prim[i]);
ans=(ans*pow(prim[i],num,M))%M;
}
return ans;
}
int main()
{
int m,n;
while(~scanf("%d%d",&m,&n),m&&n)
{
printf("%d\n",combination(m,n));
}
return 0;
}
方案4:
Lucas定理，将m,n化为p进制,有:C(n,m)=C(n0,m0)*C(n1,m1)...(mod p)，算一个不是很大的C(n,m)%p,p为素数，化为线性同余方程,用扩展的欧几里德定理求解，n在int范围内，修改一下可以满足long long范围内。
[cpp]
#include
const int M = 10007;
int ff[M+5]; //打表，记录n!，避免重复计算
//求最大公因数
int gcd(int a,int b)
{
if(b==0)
return a;
else
return gcd(b,a%b);
}
//解线性同余方程，扩展欧几里德定理
int x,y;
void Extended_gcd(int a,int b)
{
if(b==0)
{
x=1;
y=0;
}
else
{
Extended_gcd(b,a%b);
long t=x;
x=y;
y=t-(a/b)*y;
}
}
//计算不大的C(n,m)
int C(int a,int b)
{
if(b>a)
return 0;
b=(ff[a-b]*ff[b])%M;
a=ff[a];
int c=gcd(a,b);
a/=c;
b/=c;
Extended_gcd(b,M);
x=(x+M)%M;
x=(x*a)%M;
return x;
}
//Lucas定理
int Combination(int n, int m)
{
int ans=1;
int a,b;
while(m||n)
{
a=n%M;
b=m%M;
n/=M;
m/=M;
ans=(ans*C(a,b))%M;
}
return ans;
}
int main(void)
{
int i,m,n;
ff[0]=1;
for(i=1;i<=M;i++) //预计算n!
ff[i]=(ff[i-1]*i)%M;
scanf("%d%d",&n, &m);
printf("%d\n",func(n,m));
return 0;
}
#include
const int M = 10007;
int ff[M+5]; //打表，记录n!，避免重复计算
//求最大公因数
int gcd(int a,int b)
{
if(b==0)
return a;
else
return gcd(b,a%b);
}
//解线性同余方程，扩展欧几里德定理
int x,y;
void Extended_gcd(int a,int b)
{
if(b==0)
{
x=1;
y=0;
}
else
{
Extended_gcd(b,a%b);
long t=x;
x=y;
y=t-(a/b)*y;
}
}
//计算不大的C(n,m)
int C(int a,int b)
{
if(b>a)
return 0;
b=(ff[a-b]*ff[b])%M;
a=ff[a];
int c=gcd(a,b);
a/=c;
b/=c;
Extended_gcd(b,M);
x=(x+M)%M;
x=(x*a)%M;
return x;
}
//Lucas定理
int Combination(int n, int m)
{
int ans=1;
int a,b;
while(m||n)
{
a=n%M;
b=m%M;
n/=M;
m/=M;
ans=(ans*C(a,b))%M;
}
return ans;
}
int main(void)
{
int i,m,n;
ff[0]=1;
for(i=1;i<=M;i++) //预计算n!
ff[i]=(ff[i-1]*i)%M;
scanf("%d%d",&n, &m);
printf("%d\n",func(n,m));
return 0;
}