POJ 3421

X-factor Chains

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 5111		Accepted: 1622

Description

Given a positive integer X, an X-factor chain of length m is a sequence of integers,

1 = X₀, X₁, X₂, …, X_m = X

satisfying

X_i < X_i₊₁ and X_i | X_i₊₁ where a | b means a perfectly divides into b.

Now we are interested in the maximum length of X-factor chains and the number of chains of such length.

Input

The input consists of several test cases. Each contains a positive integer X (X ≤ 2²⁰).

Output

For each test case, output the maximum length and the number of such X-factors chains.

Sample Input

Sample Output

Source

POJ Monthly--2007.10.06, ailyanlu@zsu

找出x的所有质因子表达式，最大长度就是各质因子指数的和，然后按照排列组合计算即可。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <iostream>
 5 
 6 using namespace std;
 7 
 8 #define maxn (1 << 20) + 5
 9 
10 typedef long long ll;
11 
12 int x,len = 0;
13 bool prime[maxn];
14 int ele[100000];
15 
16 ll cal(int x) {
17         ll ans = 1;
18         for(int i = 1; i <= x; i++) ans *= i;
19 
20         return ans;
21 }
22 
23 void init() {
24         for(int i = 2; i <= maxn - 5; i++) {
25                 prime[i] = i % 2 || i == 2;
26         }
27 
28         for(int i = 2; i * i <= maxn - 5; i++) {
29                 if(!prime[i]) continue;
30                 for(int j = i; j * i <= maxn - 5; j++) {
31                         prime[j * i] = 0;
32                 }
33         }
34 
35         len = 0;
36         for(int i = 2; i <= maxn - 5; i++) {
37                 if(prime[i])
38                 ele[len++] = i;
39         }
40 
41 
42 }
43 int main() {
44         //freopen("sw.in","r",stdin);
45 
46         init();
47 
48         while(~scanf("%d",&x)) {
49                 if(prime[x]) {
50                         printf("1 1
");
51                 } else {
52                         int ans1 = 0,len2 = 0;
53                         ll ans2 = 0;
54                         int num[30];
55                         for(int i = 0; i < len && ele[i] <= x && x != 1; i++) {
56                                 int sum = 0;
57                                 if(x % ele[i] == 0) {
58                                         while(x % ele[i] == 0) {
59                                                 ans1++;
60                                                 sum++;
61                                                 x /= ele[i];
62                                         }
63                                         num[len2++] = sum;
64                                 }
65 
66 
67                         }
68 
69                         ans2 = cal(ans1);
70                         for(int i = 0; i < len2; i++)  {
71                                 ans2 /= cal(num[i]);
72                         }
73                         printf("%d %I64d
",ans1,ans2);
74 
75                 }
76 
77         }
78 
79         return 0;
80 }

View Code