自动搬运

查看原文

来自洛谷，原作者为

	zhczcg314 生于忧患，死于安乐

搬运于2025-08-24 21:15:08，当前版本为作者最后更新于2023-06-24 21:05:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

B3801题解

题目传送门

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

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

看条件：

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

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

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

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

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