题意：给n和k，求组合C(n,k)的因子个数。
这道题，若一开始先预处理出C[i][j]的大小，再按普通方法枚举2~sqrt(C[i][j])来求解对应的因子个数，会TLE。
所以得用别的方法。
在说方法前，先说一个n!的性质：
n!的素因子分解中的素数p的个数为
n/p+n/(p^2)+...+n/(p^k)+...
《ACM-ICPC程序设计系列 数论及应用》上的方法，200+ms：
首先先求解435以内的素因子。
然后预处理出j!中每个素因子的个数，公式如下：
num[j][i]=j/prime[i]+num[j/prime[i]][i];
设n!中素因子p的个数为：a=n/p+n/(p^2)+...+n/(p^k)+...
那么(n/p)!中素因子p的个数为：b=n/(p^2)+...+n/(p^k)+...
很显然a=b+n/p，因此可以利用上述递推公式预处理出所有的j!中每个素因子的个数。
接下来就可以预处理出C(i,j)的因子个数，然后一切就好办了。
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <math.h> using namespace std;
const int maxn=;
bool isprime[maxn];
int prime[maxn];
int cnt=;
int num[maxn][maxn]; //num[i][j]表示i!中素因子prime[j]的个数。
long long C[maxn][maxn]; //C[i][j](0<=j<=i)表示组合C(i,j)的因子个数。
void init(){
memset(isprime,true,sizeof(isprime));
for(int i=;i<maxn;i++){
if(isprime[i]){
prime[cnt++]=i;
for(int j=i*;j<maxn;j+=i)
isprime[j]=false;
}
}
memset(num,,sizeof(num));
for(int i=;i<cnt;i++){
for(int j=;j<maxn;j++)
num[j][i]=j/prime[i]+num[j/prime[i]][i];
}
//预处理出C(i,j)的因子个数
for(int i=;i<maxn;i++){
for(int j=;j<i;j++){
C[i][j]=;
for(int k=;k<cnt;k++){
int d=num[i][k]-num[i-j][k]-num[j][k];
if(d)
C[i][j]*=d+;
}
}
}
}
int main()
{
init();
int n,k;
while(scanf("%d%d",&n,&k)!=EOF){
if(n==k ||k==)
printf("1\n");
else
printf("%I64d\n",C[n][k]);
}
return ;
}
我的方法没有预处理，每次读取n和k后，利用公式计算n!,k!,(n-k)!的各个因素的个数，最后再总的求。时间600多ms。
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <math.h> using namespace std;
const int maxn=;
bool isprime[maxn];
int prime[maxn];
int cnt=;
int num[maxn];
void init(){
memset(isprime,true,sizeof(isprime));
for(int i=;i<maxn;i++){
if(isprime[i]){
prime[cnt++]=i;
for(int j=i*;j<maxn;j+=i)
isprime[j]=false;
}
}
}
//求n!的各个素因子的个数
void countnum1(int n){
for(int i=;i<cnt && prime[i]<=n;i++){
int c=,p=prime[i];
while(n/p){
c+=n/p;
p*=prime[i];
}
num[prime[i]]+=c; //在分子上，是+=c。 }
}
void countnum2(int n){
for(int i=;i<cnt && prime[i]<=n;i++){
int c=,p=prime[i];
while(n/p){
c+=n/p;
p*=prime[i];
}
num[prime[i]]-=c; //分母，是-=c
}
}
int main()
{
init();
int n,k;
while(scanf("%d%d",&n,&k)!=EOF){
memset(num,,sizeof(num));
countnum1(n);
countnum2(n-k);
countnum2(k);
long long ret=;
for(int i=;i<cnt;i++){
if(num[prime[i]]){
ret*=(num[prime[i]]+);
}
}
printf("%I64d\n",ret);
}
return ;
}