题目大意：求C(n, k)的约数个数

预备知识：

n!分解素因子

    C(n, k) = n!/(k! * (n-k)!) 显然我们只要求出C(n,k)的素因子及其个数就可以了. 首先我们是可以知道n!的素因子的：1~n的素数，又因为C(n, k)是整数，显然k!和(n-k)!的素因子n!都有. 那么我们枚举n!的素因子，

C(n,k)的素因子p的个数 = f(n, p) - f(k, p) - f(n-k, p).     （f(n ,p)表示n!中素因子p的个数） 然后+1乘起来即可.   PS：这题POJ的数据逆天啊……N多组数据……必须先把所有函数都预处理用数组记录下来，不然会TLE……  

#include #include #include using namespace std;int ff[450][450];   //预处理f(n, p)int f(int n, int p){    long long res = 0;    while(n){        res += n/p;        n /= p;    }    return res;}vector  > prime;     //n!的素因子就是1~n中的素数,第一个记录素因子,第二个记录个数bool noprime[440];void Prime(){    prime.clear();    for (int i = 2; i <= 431; i ++){        if (!noprime[i]){            prime.push_back(make_pair(i, 0));            for (int j = i; j <=431; j ++)                ff[j][i] = f(j, i);        }        for (int j = 0; j < prime.size() && prime[j].first*i <= 431; j ++){            noprime[prime[j].first*i] = 1;            if (i % prime[j].first == 0)                break;        }    }}long long ans[450][450];    //预处理factor(n,k)long long factor(int n, int k){    long long res = 1;    for (int i = 0; i < prime.size(); i ++){        if (prime[i].first > n)            break;        int p = prime[i].first;        prime[i].second = ff[n][p];        if (p <= k)            prime[i].second -= ff[k][p];        if (p <= (n - k))            prime[i].second -= ff[n-k][p];        res *= (prime[i].second + 1);    }    return res;}int main(){    Prime();    int n, k;    for (int i = 0; i <= 431; i ++){        for (int j = 0; j <= i; j ++)            ans[i][j] = factor(i, j);    }    while(scanf("%d%d", &n, &k) == 2){        printf("%I64d\n", ans[n][k]);    }    return 0;}