五边形数定理证明

$$ \varphi(x) = \sum_k (-1)^k x^{\frac{k(3k+1)}{2}}$$

欧拉函数的倒数是划分数的生成函数:

$\frac{1}{\varphi(x)} = \sum p(i)x^i = \prod \frac{1}{1-x^i}$。

定义可以知道 $\varphi(x) \times \frac{1}{\varphi(x)} = 1$

代入: $(\sum (-1)^k x^{\frac{k(3k+1)}{2}})(\sum p(i) x^i) = 1$

即为 $(1-x-x^2+x^5+x^7…)(1+p(1)x+p(2)x^2…)=1$

可知 $p(k) = p(k-1)+p(k-2)-p(k-5)…$。

通过这个我们可以得到 $\sum p(i)x^i$，前者的项数是 $\sqrt n$ 的，所以总体复杂度是 $O(n \sqrt n)$。

如果限定拆分出来最大的数 $<k$，那么可以用类似的做法（等比数列求和然后转成欧拉函数相关）

$F(x) = \prod \frac{(1-x^k)}{1-x} = \frac{\varphi(x ^ k)}{\varphi(x)}$。

这相当于 $F(x) = \varphi(x^k) \times P(x)$。（相当于卷积，单项可以做到 $O(\sqrt n)$）

另一种 $n \sqrt n$ 的做法。

对于 $x \leq \sqrt n$ 的，直接完全背包。

对于$x > \sqrt n$ 的，可以用一个状态 $f_{i,j}$ 表示装了 $i$ 个物品，大小为 $j$。

那么其实就是 $f_{i, j} = f_{i-1,j-1} + f_{i,j-i}$。

前者表示在基础上加一个 ${1}$。

后者表示在所有加进来的数字整体加上一个 1。

最后答案就是 $\sum_{j = 0}^{n}(f_{j} \times \sum_{i = 0}^{\sqrt n} g_{i, n - j})。$