X-factor Chains
| Time Limit: 1000MS |
? |
Memory Limit: 65536K |
| Total Submissions: 5659 |
? |
Accepted: 1786 |
Description
Given a positive integer X, an X-factor chain of length m is a sequence of integers,
1 = X0, X1, X2, …, Xm = X
satisfying
Xi < Xi+1 and Xi | Xi+1 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 ≤ 220).
Output
For each test case, output the maximum length and the number of such X-factors chains.
Sample Input
2
3
4
10
100
Sample Output
1 1
1 1
2 1
2 2
4 6
?
题意：给你一个数X，将X分解成1~X的因子数列，前一个数可以整数后一个数，求满足条件的最大链长以及有多少条这样长的链。
分析：很容易想到了素因数分解。不难推出，我们要求的最大链长就等于素因子的个数，最长链条数就是这些素因子的排列组合数。题目数据量较大，所以先打个素数表。
题目链接：http://poj.org/problem?id=3421
代码清单：
?
#include
#include