Day7 - G - Divisors POJ

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?

Input

The input consists of several instances. Each instance consists of a single line containing two integers n and k (0 ≤ k ≤ n ≤ 431), separated by a single space.

Output

For each instance, output a line containing exactly one integer -- the number of distinct divisors of C_n^k. For the input instances, this number does not exceed 2 ⁶³ - 1.

Sample Input

Sample Output

2

6

16

思路：求因数个数，想到唯一分解定理
p = a1^s1+a2^s2+...., 因子总数=(s1+1)(s2+1)..... 每次都计算组合数再计算因子数显然会超时，范围只有431，可以预处理
先预处理出质数，由C[n][m] = n!/m!(n-m)!, 将每个阶乘中的质因子次数求出来，例如对于n!,求质数i的次数 = n/i+n/i^2+n/i^3+....
递推优化， a = n/i+n/i^2+...., b = a / i = n/i^2+n/i^3+....

typedef long long LL;

typedef pair<LL, LL> PLL;

const int maxm = ;

bool prime[maxm];

int num[maxm][maxm];

int jud[maxm], siz = ;

LL C[maxm][maxm];

void getprime() {

    for(int i = ; i * i <= maxm; ++i) {

        if(!prime[i]) {

            for(int j = i*i; j <= maxm; j += i)

                prime[j] = true;

        }

    }

    for(int i = ; i <= maxm; ++i)

        if(!prime[i]) {

            jud[siz++] = i;

        }

    for(int i = ; i < siz; ++i) {

        for(int j = ; j <= maxm; ++j)

            num[j][i] = j/jud[i] + num[j/jud[i]][i];

    }

    for(int i = ; i <= maxm; ++i) { // C[i][j]

        for(int j = ; j < i; ++j) {

            C[i][j] = ;

            for(int k = ; k < siz; ++k) {

                int d = num[i][k] - num[i-j][k] - num[j][k];

                if(d) C[i][j] *= (d+);

            }

        }

    }

}

int main() {

    getprime();

    int n, k;

    while(scanf("%d%d", &n, &k) != EOF) { // C(n, k) n!/k!(n-k)!

        if(n == k || k == )

            printf("1\n");

        else

            printf("%lld\n", C[n][k]);

    }

    return ;

}

巴特西

Day7 - G - Divisors POJ - 2992

最新文章

热门文章