https://vjudge.net/problem/POJ-3421#author=GPT_zh
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 ≤ 2^20).
Output
For each test case, output the maximum length and the number of such X-factors chains.
2
3
4
10
100
1 1
1 1
2 1
2 2
4 6
给定一个正整数 X,长度为 m 的 X 因子链是一个整数序列,1 = X0, X1, X2, …, Xm = X
满足Xi < Xi+1 且 Xi | Xi+1,其中 a | b 表示 a 完全整除 b。
现在我们对 X 因子链的最大长度和该长度的链的数量感兴趣。
输入
输入包含多个测试用例。每个测试用例包含一个正整数 X (X ≤ 2^20)。
输出
对于每个测试用例,输出最大长度和该长度的 X 因子链的数量。
2
3
4
10
100
1 1
1 1
2 1
2 2
4 6
解答:
一道好题目 可以用多种方案解决
- 分解约数 dp得到最长路径和最长路径数目
- 分解质因数 dfs获得最长路径的数目
- 分解质因数 使用排列组合直接得到最长路径数目