POJ 2992（求C(n,k)的约数个数）

首先肯定不可能一个一个进行计算
采用数论中的相关知识可以得到求解本题的两个公式，
对于任于的数p=n1p1∗n2p2∗n3p3.....$p=n{1}^{p}1\ast n{2}^{p}2\ast n{3}^{p}3.....$
p的因数个数为(1+p1)∗(1+p2)∗(1+p3)....$(1+p1)\ast (1+p2)\ast (1+p3)....$ （1）
n!的质因子p的个数为n/p+n/(p2)+n(p3)+...$n/p+n/(p^2)+n(p^3)+...$
再由组合数学中的公式 c(n,m)=n!/(m!∗(n−m)!$c(n,m)=n!/(m!\ast (n-m)!$ 只要求出n！的所有对应的质因子个数，然后减去相应的m！的所有对应的质因子个数和(n-m)！的所有对应的质因子个数然后套用（1）式进行计算。

#include <cstdio>

using namespace std;

typedef long long ll;

ll jie[440][100];  ///jie[i][j]表示i的阶乘中第j个素数的个数。
ll C[440][440];    ///打表解出C[i][j]的因子个数
int p[100];
bool book[440];
int len;

void quick_pri(){
    book[0]=book[1]=1;
    for(int i=2;i<440;i++){
        if(!book[i]) p[len++]=i;
        for(int j=0;j<len&&i*p[j]<440;j++){
            book[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
}

int main()
{
    quick_pri();
    for(int j=0;j<len;j++){
        for(int i=2;i<440;i++){
            jie[i][j]=i/p[j]+jie[i/p[j]][j];
        }
    }
    for(int i=2;i<440;i++){
        for(int j=1;j<i;j++){
            C[i][j]=1;
            for(int k=0;k<len&&jie[i][k];k++){
                int num=jie[i][k]-jie[j][k]-jie[i-j][k];
                if(num) C[i][j]*=(num+1);
            }
        }
    }
    int n,k;
    while(scanf("%d%d",&n,&k)!=EOF){
        if(k==0||k==n){
            printf("1\n");continue;
        }else{
            printf("%lld\n",C[n][k]);
        }
    }
    return 0;
}