题目链接：
题目要求：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#include #include #include #include #define N 500using namespace std;typedef long long ll;bool b[N];int n,k,i,num[N],prime[N],top;__int64 sum;int main(){ top=0; b[0]=b[1]=false; b[2]=true; for(i=3; i<440; i++) if(i%2==0) b[i]=false; else b[i]=true; double t=sqrt(440*1.0); for(i=3; i<=t; i++) { if(b[i]) { for(int j=i*i; j<440; j=j+i) b[j]=false; } } for(i=2;i<=440;i++) { if(b[i]) { prime[top++]=i; } } while(scanf("%d%d",&n,&k)!=EOF) { sum=1; memset(num,0,sizeof(num)); int X=0,t,z; for(i=prime[0];i<=n;i=prime[++X]) { t=n; z=i; while(t/z)//核心部分 { num[i]+=t/z; z*=i; } } X=0; for(i=prime[0];i<=n-k;i=prime[++X]) { t=n-k; z=i; while(t/z) { num[i]-=t/z; z*=i; } } X=0; for(i=prime[0];i<=k;i=prime[++X]) { t=k; z=i; while(t/z) { num[i]-=t/z; z*=i; } } for(int i=2; i<=n; i++) { if(num[i]) { sum*=(num[i]+1); } } printf("%I64d\n",sum); } return 0;}
暴力到死的代码：
#include#include #include #include #include #define N 500using 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=1; memset(num,0,sizeof(num)); if(k>n/2) k=n-k; for(int z=n-k+1;z<=n;z++) { i=z; for(int j=2;j*j<=i;j++) { if(i%j==0) { num[j]++; i/=j; while(i%j==0) { num[j]++; i/=j; } } } if(i!=1) num[i]++; } for(int z=2;z<=k;z++) { i=z; for(int j=2;j*j<=i;j++) { if(i%j==0) { num[j]--; i/=j; while(i%j==0) { num[j]--; i/=j; } } } if(i!=1) num[i]--; } for(int i=2;i<=n;i++) { if(num[i]) { num[i]++; //printf("___%d %d\n",i,num[i]); } } for(int i=2;i<=n;i++) { if(num[i]) { sum*=num[i]; } } printf("%lld\n",sum); } return 0;}