B3801题解

· · 题解

B3801题解

题目传送门

这是一篇写给自己的题解 说白了就是写的比较浅，易懂。

给定 n,k，去统计符合给定三个要求序列的结果的个数。

看条件：

第一、三个条件中给到了 n，那么分析一下：有 k 个数字的乘积是 n，且他们的最小公倍数还是 n，我们可以得到这 k 个数两两互质。

再来看第二个条件，这 k 个数的序列是非严格单调递增的序列。（没什么用）

那么分析到这里，大概可以感觉到这道题的解法了：先将 n 分解质因数，得到质因数的种类数（注意这里是种类数，不是个数），所有的这些质因数都需要参加到序列的组建中，而数列的长度是 k，那么假设质因数种类数大于 k，就需要将质因数两两配对或者多个配对，即将它们相乘，最后得出 k 个数字，就是这个序列。但是这里注意一个特殊情况，如果最后求出来的质因数种类数小于 k，那么就没有分配策略了，直接特判，答案为 0。

而这道题的问题是要去找序列的个数，那么我非常自然地想到之前做过的一道题，解法和这个类似，学生分组。看到大佬说的第二类斯特林数，我不禁低下了头……第二类斯特林数的直观体现其实就是上面贴的那个问题，有兴趣的可以去了解一下。

看到这差不多就可以写代码了，加油吧~~