POJ2992:Divisors（求N！因子的个数，乘性函数，分解n!的质因子（算是找规律））

题目要求：Your task in this problem is to determine the number of divisors of C_n^k. 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);（求因子的个数的公式）

这题是求C_n^k. 直接求肯定超时，所以要找规律，我没有找到，看了大神的题解，求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=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
",sum);
    }
    return 0;
}

暴力到死的代码：

#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=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
",i,num[i]);
            }

        }
        for(int i=2;i<=n;i++)
        {
            if(num[i])
            {
               sum*=num[i];
            }
        }
        printf("%lld
",sum);
    }
    return 0;
}

View Code