10206. 「一本通 6.3 练习 1」X-factor Chain

题意

输入正整数 $x$,求 $x$ 的大于 $1$ 的因子组成的满足任意前一项都能整除后一项的序列的最大长度,以及满足最大长度的序列的个数。

思路

题目读起来很困难?告诉你题目的实际意思。 给你一个数,要求你输出将这个数分解成因式相乘,并且后面一个因子至少是前面一个因子的2倍,问最长的因式相乘链有多长,有几条最长的因式相乘链。 为什么可以这样转化呢? 拿个样例来看看。 $$100=2^2*5^2$$ 所以最长的序列长度为4,可以是这样的:100,50,25,5。 那是不是就是直接从原数不断除就好了,所以题面就相当于上述。 将读入的那个数字进行分解质因数。分解出来自然后面一个数必然大于前面一个数的两倍。 满足最大长度的序列的个数 ,就是全排列。但是要除去重复因子的全排列。所以$n$个不同的数的全排列就是$n!$,除去重复的就是$n!$除以每个重复因子数的阶乘。
暂无评论

发送评论


				
上一篇
下一篇