CC

自然万物都趋向从有序变得无序

0%

Divisors POJ - 2992

发表于 更新于 分类于 Valine：

题目链接

题目

Your task in this problem is to determine the number of divisors of Cnk. 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 Cnk. For the input instances, this number does not exceed 2 63 - 1.

Sample Input

5 1
6 3
10 4

Sample Output

2
6
16

题意:

求组合数的因子个数.

思路:

大概就是将组合数写成阶乘的形式, 然后统计每个质数因子的个数即可.

代价:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;
const int maxn = 500;
int pri[maxn];
int a[maxn];
int b[maxn];
bool vis[maxn];
int num;

void prime(){
    num = 0;
    memset(vis, false, sizeof(vis));
    for(int i = 2; i < maxn; ++i){
        if (!vis[i]) pri[++num] = i;
        for(int j = 1; j <= num && i * pri[j] < maxn; ++j){
            vis[ i* pri[j]] = true;
            if (i % pri[j] == 0) break;
        }
    }
}

int solve(int n, int t){
   int ans = 0;
   int x = t;
   while(t <= n){
         ans += n / t;
         t *= x;
   }return ans;
}

int main(){
    //ios::sync_with_stdio(false);
    int n, m;
    prime();
    while(scanf("%d %d", &m, &n) != EOF){
     //   if(n > m / 2) n = m - n;
        LL ans = 1;
       for(int i = 1; i <= num &&  pri[i] <= m; ++i)
            ans *=(solve(m, pri[i]) - solve(n, pri[i]) - solve(m - n, pri[i]) + 1);
      printf("%lld\n",ans);
    }return 0;
}