题目链接：http://poj.org/problem?id=2992
题目要求：Your task in this problem is to determine the number of divisors of Cnk. Just for fun -- or do you need any special reason for such a useful computation?
题目解析：这题也是TLE了无数遍，首先说一下求因子数目的函数是积性函数，积性函数即f(n)=f(a)*f(b),a与b互质并且a*b==n,因为n很大，所以要利用积性函数的性质，将n分解质因数，然后求其质因数的因子和，之后相乘即可，公式如下：
定理：设正整数n的所有素因子分解n=p1^a1*p2^a2*p3^a3****Ps^as,那么
T(n)=(a1+1)*(a2+1)*(a3+1)***(an+1);（求因子的个数的公式）
这题是求Cnk. 直接求肯定超时，所以要找规律，我没有找到，看了大神的题解，求N！质因子的规律如下，
首先，我们可以把所有的N以内的质数给打表求出来
然后，求每一个质因子的指数个数，这里用到了一个公式，：
ei=[N/pi^1]+ [N/pi^2]+ …… + [N/pi^n] 其中[]为取整
附：这一步最近又想到了一个更好的方法 int ei=0;while(N) ei+=(N/=pi); 怎么样？？
（想一想为什么，实在想不通你就举个例子试一下）
最后，就是套公式计算了，M=（e1+1）*（e2+1）*……*（en+1）
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#define N 500
using namespace std;
typedef long long ll;
bool b[N];
int n,k,i,num[N],prime[N],top;
__int64 sum;
int main()
{
top=;
b[]=b[]=false;
b[]=true;
for(i=; i<; i++)
if(i%==) b[i]=false;
else b[i]=true;
double t=sqrt(*1.0);
for(i=; i<=t; i++)
{
if(b[i])
{
for(int j=i*i; j<; j=j+i)
b[j]=false;
}
}
for(i=;i<=;i++)
{
if(b[i])
{
prime[top++]=i;
}
}
while(scanf("%d%d",&n,&k)!=EOF)
{
sum=;
memset(num,,sizeof(num));
int X=,t,z;
for(i=prime[];i<=n;i=prime[++X])
{
t=n;
z=i;
while(t/z)//核心部分
{
num[i]+=t/z;
z*=i;
}
}
X=;
for(i=prime[];i<=n-k;i=prime[++X])
{
t=n-k;
z=i;
while(t/z)
{
num[i]-=t/z;
z*=i;
}
}
X=;
for(i=prime[];i<=k;i=prime[++X])
{
t=k;
z=i;
while(t/z)
{
num[i]-=t/z;
z*=i;
}
}
for(int i=; i<=n; i++)
{
if(num[i])
{
sum*=(num[i]+);
}
}
printf("%I64d\n",sum);
}
return ;
}
暴力到死的代码：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#define N 500
using namespace std;
typedef long long ll; int n,k,i;
int num[N];
ll sum;
int main()
{
while(scanf("%d%d",&n,&k)!=EOF)
{
sum=;
memset(num,,sizeof(num));
if(k>n/)
k=n-k;
for(int z=n-k+;z<=n;z++)
{
i=z;
for(int j=;j*j<=i;j++)
{
if(i%j==)
{
num[j]++;
i/=j;
while(i%j==)
{
num[j]++;
i/=j;
}
}
}
if(i!=)
num[i]++;
}
for(int z=;z<=k;z++)
{
i=z;
for(int j=;j*j<=i;j++)
{
if(i%j==)
{
num[j]--;
i/=j;
while(i%j==)
{
num[j]--;
i/=j;
}
}
}
if(i!=)
num[i]--;
}
for(int i=;i<=n;i++)
{
if(num[i])
{
num[i]++;
//printf("___%d %d\n",i,num[i]);
} }
for(int i=;i<=n;i++)
{
if(num[i])
{
sum*=num[i];
}
}
printf("%lld\n",sum);
}
return ;
}