题解：AT_abc461_f [ABC461F] Total Product is N

Re_FYCCCCTA · 2026-06-07 15:38:40 · 题解

AT_abc461_f Total Product is N

考场上怎么全想暴搜了……

神图。

设 \{d_i\} 为 n 的因数集合，其大小为 m。考虑 dp，设 f_{i,j,k},g_{i,j,k} 分别表示考虑前 i 个因数，选了 j 个，因数乘积为 k 时的方案数 / 分数，这里不考虑顺序。则答案为 \sum_i g_{m,i,n}\times i!。

转移时，枚举三维，考虑 d_i 是不是 k 的因数：

• 如果 d_i \mid k，则考虑选不选 d_i：

  • f_{i,j,k}=f_{i-1,j,k}+f_{i-1,j-1,\frac{k}{d_i}}
  • g_{i,j,k}=g_{i-1,j,k}+(g_{i-1,j-1,\frac{k}{d_i}}+f_{i-1,j-1,\frac{k}{d_i}}\times d_i)

• 如果 d_i \nmid k，则两者都只能从 (i-1,j,k) 的状态转移过来。

接下来我们来分析时间复杂度：

• 即使尽可能小地选择因数，即依次选 1,2,3,\dots，到 14 时就有 14!>10^{10}，于是第二维只用枚举到 14。

于是总时间复杂度为 O(14m^2)，看表，m\le 2304，可以通过！

这种和因数有关的题目感觉能有因数个数不多的直觉很重要啊！

代码