题目链接
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);}
}
在参考大神们的题意分析时,见到了一句比较值得注意的话:
(不开longlong见祖宗,十年OI一场空)
哈哈,与君共勉~