1 条题解

  • 0
    @ 2018-03-28 20:02:36

    计算每一个f[i]对x的贡献
    那么i肯定是x的约数,枚举x的约数d,那么贡献即是f[d]*calc(n/d)
    calc(n/d)即是计算n/d被分解成k个正整数乘积的方案数,因为每次d都会至少乘上一个正整数,最终达到x。那么考虑n/d的每个素因子p,p^m|n/d,那么这个素因子的贡献就是乘上C(m+k-1,k-1),即相当于把m个数分成k份,并且允许为空

  • 1

信息

难度
9
分类
(无)
标签
(无)
递交数
7
已通过
1
通过率
14%
上传者