POJ 2992 质因子分解

题意要求出C(n,k)的因子个数 所以就需要把C(n,k)质因子分解 这题数据非常变态 我的思路没问题但是无数次TLE之后我才发现应该先打出一个 n!的一个表 不然就超时 用C(n,k)=n!/(k!*(n-k)!) 这个公式就可以求出

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define max 435
int prime[max],nprime;
bool isprime[max];
void getprime()
{
    long long i,j;
    memset(isprime,1,sizeof(isprime));
    isprime[1]=0;
    nprime=0;
    for(i=2; i<max; i++)
        if(isprime[i])
        {
            prime[++nprime]=i;
            for(j=i*i; j<max; j+=i)
                isprime[j]=0;
        }
}
long long a[435][435];
void getnum()
{
    memset(a,0,sizeof(a));
    for(int s=1; s<=431; s++)
    {
        int x=s;
        memcpy(a[s],a[s-1],sizeof(a[s]));
        if(isprime[x])
        {
            a[s][x]++;
            continue;
        }
        for(int i=1; prime[i]<=x,x>1; i++)
            while(x%prime[i]==0&&prime[i]>0)
            {
                a[s][prime[i]]++;
                x/=prime[i];
            }
    }
}
int main()
{
    getprime();
    getnum();
    int n,k;
    long long ans;
    while(~scanf("%d%d",&n,&k))
    {
        ans=1;
        for(int i=2; i<=n; i++)
            if(a[n][i]-a[k][i]-a[n-k][i])
                ans*=(a[n][i]-a[k][i]-a[n-k][i]+1);
        printf("%lld\n",ans);
    }
    return 0;
}