poj2992 阶乘分解

/*
将C(n,k)质因数分解,然后约束个数按公式计算
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long int v[],prime[],m,c[],p[];
void init(int n){
memset(prime,,sizeof prime);
memset(v,,sizeof v);
m=;
for(int i=;i<=n;i++){
if(v[i]==){
v[i]=i;
prime[++m]=i;
}
for(int j=;j<=m;j++){
if(prime[j]>v[i] || prime[j]*i>n) break;
v[i*prime[j]]=prime[j];
}
}
}
int cal(int p,int n){
int ret=,tmp=p;
while(tmp<=n){
ret+=n/tmp;
tmp*=p;
}
return ret;
} int main(){
int n,k;
init();
while(scanf("%d%d",&n,&k)==){
memset(c,,sizeof c);
memset(p,,sizeof p);
ll ans=;
for(int i=;i<=m;i++){
if(prime[i]>n) break;
c[i]+=cal(prime[i],n);
}
for(int i=;i<=m;i++){
if(prime[i]>n-k)break;
c[i]-=cal(prime[i],n-k);
}
for(int i=;i<=m;i++){
if(prime[i]>k) break;
c[i]-=cal(prime[i],k);
}
for(int i=;i<=m;i++)
if(c[i]) ans*=(c[i]+);
printf("%lld\n",ans);
}
}
上一篇:vagrant之常用操作


下一篇:如何使用PowerDesigner设计数据库关系模式