Divisors
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 263 - 1.
Sample Input
5 1
6 3
10 4
Sample Output
2
6
16
Source
题目类型：阶乘素因子分解
算法分析：将440以内的阶乘的素因子求出来，使用f[i][j]表示阶乘i的素因子j的个数有多少个，然后对于每个n和k，计算f[n][i] - f[n-k][i] - f[k][i]表示组合(n,k)中素因子为i的指数个数，然后直接累乘起来
|
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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 7; const int maxn = 666 + 66; bool prime[maxn]; int primelist[maxn], num; int f[maxn][maxn]; void GetPrime () { memset (prime, true, sizeof (prime)); num = 0; int i; for (i = 2; i <= maxn; i++) { if (prime[i]) primelist[num++] = i; int j; for (j = 0; j < num; j++) { if (i * primelist[j] > maxn) break; prime[i*primelist[j]] = false; if (i % primelist[j] == 0) break; } } } int Solve (int val, int fa) { int sum = 0, temp = fa; while (val / fa) { sum += val / fa; fa *= temp; } return sum; } int main() { // ifstream cin ("aaa.txt"); // freopen ("aaa.txt", "r", stdin); GetPrime (); for (int i = 1; i <= 440; i++) { for (int j = 0; j < num; j++) f[i][j] = Solve (i, primelist[j]); } long long n, k; while (scanf ("%d%d", &n, &k) != EOF) { long long ans = 1; for (int i = 0; i < num && primelist[i] <= n; i++) ans *= (f[n][i] - f[n-k][i] - f[k][i] + 1); printf ("%lld\n", ans); } return 0; } |
- « 上一篇：poj2955
- poj3061：下一篇 »