这道题太神奇了，这么久我才理解了一点。。。。

接下来就是照打了
原题链接

这种题目考虑背包，
$dp[i][j]$dp[i][j]表示枚举到第i个数，乘积为j的方案总数，
而易推知$dp[i]只和dp[i-1]$dp[i]只和dp[i−1]有关，用经典的背包降维，
即$dp[j]=max(dp[j],dp[j/k]+1),k$dp[j]=max(dp[j],dp[j/k]+1),k表枚举可整除j的n的因数（n是输入的数）
而因为不能重复使用，我们再套用经典的逆序背包即可

$$
但数据范围很大，所以上述做法显然是不行的（i，j都要枚举）（数组要开1e12）TLE+MLE

---

前置知识

即i为因子fac的下标

• 当$fac&lt;=\sqrt{n}$fac<=n​ 则 记录fac的下标记录为pos1=i
• 当$fac&gt; \sqrt{n}$fac>n​ 则 记录fac的下标记录为pos2=i
• 这样我们可以优化空间，空间复杂度降为√n

---

我们考虑转换状态，每次枚举可整除j的因数k,即我们可以以k为状态，枚举以k为因子j的数
但还是不行（枚举以k为因子的数j还是会TLE）
这时我们考虑枚举m，使得k*m=j
但为了避免重复计算，我们考虑不妨设k为j的最大因子
由于有了前置知识，所以我们可以只枚举编号,用$fac和pos$fac和pos 转换，

$$

dp[i][j] 表示将编号为i的因子fac[i]拆分，使拆分到的每一个数均<=fac[j]

为了方便记录初始状态，我们不妨记录每一个数都可以拆成自己，最后减1即可，
（因为比如42=67） 我们可以用6,7转移，但7不能拆，方案数为0，而根据乘法原理01=0，显然不对
$$
讨论dp[i][j]的转移
$dp[i][j]+=dp[i][j-1]$dp[i][j]+=dp[i][j−1] 直接继承,分不到$fac_j$facj​，即分$fac_i&lt;=fac_{j-1}$faci​<=facj−1​的个数
$if(i==j)dp[i][j]++$if(i==j)dp[i][j]++ 算上这个数本身
$if$if$(fac_i$(faci​ % $fac_j==0)$facj​==0) 即$fac_i$faci​有$fac_j$facj​这个因子，由于我们没统计过含有$fac_j$facj​的个数，那我们
不妨提出$fac_j$facj​,又因子不能重复，我们只需要用$ \color $