[CCC2018] 平衡树
题目描述
**题目译自 [CCC 2018](https://cemc.math.uwaterloo.ca/contests/computing/2018/) S4「[Balanced Trees](https://cemc.math.uwaterloo.ca/contests/computing/2018/stage%201/seniorEF.pdf)」**
我们定义「完美平衡树」如下:
每棵完美平衡树都有一个正整数权值。权值为 $1$ 的完美平衡树为只含有 $1$ 个节点的树。否则,这棵树的权值为 $w(w\ge2)$,则这棵树为一棵含有 $k(2\le k\le w)$ 棵子树的有根树。所有的 $k$ 棵子树都必须是相同的,且它的所有 $k$ 棵子树必须完全相同,且自身是完美平衡的。
特别地,所有 $k$ 棵子树权值必须相同。它们的权值必须为 $\left\lfloor\frac{w}{k}\right\rfloor$ 。例如,如果一棵权值为 $8$ 的完美平衡树有 $3$ 棵子树,那么每棵子树的权值为 $2$,因为 $2+2+2=6\le8$。
给定 $N$,求出权值为 $N$ 的完美平衡树的数量。
输入输出格式
输入格式
输入包含一行一个整数 $N$。
输出格式
输出一个整数表示权值为 $N$ 的完美平衡树的数量。
输入输出样例
输入样例 #1
4
输出样例 #1
3
输入样例 #2
10
输出样例 #2
13
说明
#### 样例解释 1
合法的树如下:
- 一棵以有 $4$ 棵权值为 $1$ 的子树为根的完美平衡树;
- 一棵以有 $2$ 棵权值为 $2$ 的子树为根的完美平衡树;
- 一棵以有 $3$ 棵权值为 $1$ 的子树为根的完美平衡树。
对于 $33\%$ 的数据,$N\le1000$;
对于另外 $13\%$ 的数据,$N\le5\times 10^4$;
对于另外 $13\%$ 的数据,$N\le10^6$;
对于全部的数据,$1\le N\le10^9$。