POJ 3421 - X-factor Chains

http://poj.org/problem?id=3421

概要

正の整数 X に対し，長さ m の X-factor chain は

• X[0] = 1
• X[m] = X
• X[i] < X[i+1]
• X[i+1] は X[i] で割りきれる

というような数列 X[i] である． 与えられた X に対して，作れる最大の数列の長さ m と，その長さになる数列がいくつあるか答える．

制約

• X <= 2^20

解法

X の素因数で順に割っていってできる数列が最大の長さ． そのような数列の数は素因数の重複組み合わせを数えればいい．

 1 #include <cstdio>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   long long fact[21];
 8   fact[0] = 1LL;
 9   for (int i = 1; i <= 20; i++) {
10     fact[i] = i*fact[i-1];
11   }
12 
13   vector<int> primes;
14   static const int M = (1<<11);
15   static bool sieve[M+1];
16   for (int i = 2; i <= M; i++) {
17     if (!sieve[i]) {
18       primes.push_back(i);
19       for (int j = i+i; j <= M; j += i) {
20         sieve[j] = true;
21       }
22     }
23   }
24 
25   int x;
26   while (scanf("%d", &x) != EOF) {
27     int a = 0;
28     long long b = 1LL;
29     for (vector<int>::const_iterator it = primes.begin(); it != primes.end() && *it <= x; ++it) {
30       int c = 0;
31       while (x % *it == 0) {
32         x /= *it;
33         ++c;
34       }
35       a += c;
36       b *= fact[c];
37     }
38     if (x != 1) {
39       ++a;
40     }
41     printf("%d %lld\n", a, fact[a]/b);
42   }
43   return 0;
44 }