POJ 3421 X-factor Chains 分解素因数+排列组合

本文主要是介绍POJ 3421 X-factor Chains 分解素因数+排列组合，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

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的因子组成的满足任意前一项都能整除后一项的序列的最大长度，以及满足该长度的所有不同序列个数。

看了大神们的博客才明白了题意，我这个小渣渣的英语水平还是有待提高呀。。。

解题思路：
弄懂了题意之后，我们可以发现题目的本质是对给定的 x 进行素因数分解，然后每次拿出一个素因数乘以前面的一个数，最终可以得到一个满足题目要求且长度最长的数列。
那么如何求满足该长度的所有不同序列个数呢？这便会用到排列组合的知识了。问有多少条链，其实就是问所有因子的全排列有多少种，但是注意要除去重复因子的全排列。n个不同的数的全排列就是n！，如果要除去重复的排列，那便让n！再除以每个素因数幂指数的阶乘。

AC代码：

#include<iostream>
#include<stdio.h>
using namespace std;
long long jiecheng(int x) {//求x的阶乘if (x != 1) return x*jiecheng(x - 1);return 1;
}
int prime[1050];
bool mark[1050];
int cnt = 0;
void init() {//素数筛法for (int i = 1; i <= 1025; i++) {mark[i] = false;}for (int i = 2; i <= 1025; i++) {if (mark[i])continue;prime[++cnt] = i;for (int j = i * 2; j <= 1025; j+=i) {mark[j] = true;}}
}
int main() {int x;init();while (scanf("%d", &x)!=EOF) {int ansPrime[30];int ansNum[30];int ansCnt = 0;for (int i = 1; i <= cnt; i++) {if (x%prime[i] == 0) {ansPrime[++ansCnt] = prime[i];ansNum[ansCnt] = 0;while (x%prime[i] == 0) {ansNum[ansCnt]++;x /= prime[i];}if (x == 1)break;//提前剪枝}}if (x != 1) {ansPrime[++ansCnt] = x;ansNum[ansCnt] = 1;}int ans = 0; long long fenmu = 1;for (int i = 1; i <= ansCnt; i++) {ans += ansNum[i];fenmu = fenmu*jiecheng(ansNum[i]);}long long fenzi = jiecheng(ans);long long num = fenzi / fenmu;printf("%d %lld\n", ans, num);}
}