题目大意

定义一种完美平衡树：

权值为 $1$ 的树是单节点树

权值为 $w \ge 2$ 的树有 $k$ 棵完全相同的子树 ($2 \le k \le w$)

每棵子树的权值为 $\lfloor w/k \rfloor$

给定 $N$，求权值为 $N$ 的完美平衡树的数量。

算法思路

核心思想

记忆化搜索 + 整除分块。

设 $f(n)$ 表示权值为 $n$ 的完美平衡树的数量。

状态转移 对于 $n \ge 2$，枚举子树个数 $k$，则每棵子树权值为 $\lfloor n/k \rfloor$：

优化技巧

1. 整除分块

注意到 $\lfloor n/k \rfloor$ 的值在连续区间内相同，可以分段计算：

对于 $l \le k \le r$，如果 $\lfloor n/l \rfloor = \lfloor n/r \rfloor$

则这段的贡献为 $f(\lfloor n/l \rfloor) \times (r-l+1)$

2. 记忆化搜索

小范围 ($n \le 10^5$) 用数组存储

大范围用 map 存储

基础情况：$f(1) = 1$

算法流程

读入 $N$

调用 get(N) 计算答案：

如果 $n=1$，返回 $1$

如果已计算过，直接返回结果

否则使用整除分块枚举所有可能的 $\lfloor n/k \rfloor$

累加贡献并存储结果

输出答案

复杂度分析

时间复杂度：$O(N^{3/4})$（整除分块 + 记忆化的复杂度）

空间复杂度：$O(N^{1/2})$（存储状态数）

总结

本题是数论与动态规划的结合：

递归定义：利用树的递归定义设计状态转移

整除分块：关键优化，将 $O(N)$ 枚举降为 $O(\sqrt{N})$ 段

记忆化搜索：避免重复计算，处理 $N \le 10^9$ 的大数据

这种"整除分块 + 记忆化"的技巧可以推广到其他涉及 $\lfloor n/k \rfloor$ 求和的计数问题，体现了数论优化在组合计数中的重要作用。