简要题面
对于正整数 \(S, n\)，求满足如下条件的素数数列 \((p_1,p_2,\cdots,p_k)\)（\(k\) 为任意正整数） 的个数：
- \(p_1\le p_2\le\cdots\le p_k\)
- \(p_1 + p_2 + \cdots + p_k = n\)
- \(\operatorname{lcm}(p_1, p_2,\cdots, p_k) = S\)
现在有一个固定 \(S\) 和多组询问 \(n\)，求答案对 \(10^9+7\) 取模后的结果
题解
显然第三条就是 \(p_1p_2\cdots p_k\) 去重后乘积 \(= S\)
所以 \(S\) 如果有平方因子，那么所有询问都输出 -1 .
我们考虑把相同的 \(p_i\) 合并，则条件变成
\[\begin{aligned}\sum p_ic_i&=n&(c_i\ge 1)\\\prod p_i &= S\end{aligned}
\]
\(c_i\ge 1\) 只需要用 \(n\) 减即可变成 \(c_i\ge 0\) .
我们发现 \(n\) 挺大，\(S\) 挺小， \(p_i\) 又还是 \(S\) 的约数，于是考虑把 \(c_i\) 对 \(\dfrac S{p_i}\) 取模
如果一个 \(c_i\) 到达了 \(\dfrac S{p_i}\)，那么就有 \(\sum\) 里面那玩意 \(=S\)
于是乎令 \(c_i = a_iS+b_i\)（\(b_i< S\)）则可以拆成俩半
- \(a_iS\)：我们称为整块
- \(b_i\)：我们称为散块
整块有个 \(S\)，可以提出来然后隔板法
散块分两类贡献
- 散块自身：因为散块非常小，跑多重背包即可
- 散块和散块合成整块：这个是要斥掉的，考虑对于 \(dp_m\)，那么减去有整块的情况 \(dp_{m-S}\)，完美解决 .
终
没了 .
reference: https://www.cnblogs.com/hzoi-DeepinC/p/11131047.html