题解：P10618 [ICPC 2013 WF] Factors

Hog_Dawa_IOI · 2025-07-09 09:24:13 · 题解

只是校内模拟赛出了这个题而已。

我们刚看到这个 n,k < 2^{63}，会觉得很头大。
我们尝试把 k 写成 p_1^{a_1} \times p_2^{a_2} \times p_3^{a_3} \times \dots \times p_N^{a_N} 的形式，这样的话 f_k=\dfrac{(\sum_{i=1}^{N} a_i)!}{\prod_{i=1}^{N} (a_i !)}。这是一个组合数问题，先把所有质因数排列，再除掉每一种相同的组合数内部打乱排列的方案。
于是我们发现这和 p 完全没有关系。
又因为我们想要让 k 尽量小，所以 p 要尽量小，尽量取到 2,3,5,7,\dots，按从小到大的顺序是最优的。
经过计算，2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23 \times 29 \times 31 \times 37 \times 41 \times 43 \times 47 \times 53 > 2^{63}-1，因此实际上我们只需要这么多个质数（一共有 16 个）。
而且我们发现这和 a_i 的顺序也没有关系。这意味着在 a_i 们相同的情况下，越大的 a_i 应该配对越小的 p_i。因此可以得到 a_1 \ge a_2 \ge a_3 \ge \dots \ge a_N。
当 a_1=63 时，k=2^{63}，刚好超出范围，因此 a_1 \le 63。

于是我们得到了两个非常重要的性质。