P4808 [CCC 2018] Balanced Trees

**This problem is translated from [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)”.** We define a “perfectly balanced tree” as follows: Each perfectly balanced tree has a positive integer weight. A perfectly balanced tree with weight $1$ is a tree with only $1$ node. Otherwise, if the tree has weight $w(w\ge2)$, then it is a rooted tree with $k(2\le k\le w)$ subtrees. All $k$ subtrees must be the same, and all of its $k$ subtrees must be exactly identical, and each subtree itself must be perfectly balanced. In particular, the weights of all $k$ subtrees must be the same. Their weight must be $\left\lfloor\frac{w}{k}\right\rfloor$. For example, if a perfectly balanced tree of weight $8$ has $3$ subtrees, then each subtree has weight $2$, because $2+2+2=6\le8$. Given $N$, find the number of perfectly balanced trees with weight $N$.

The input contains one line with one integer $N$.

Output one integer, the number of perfectly balanced trees with weight $N$.

#### Sample Explanation 1 The valid trees are: - A perfectly balanced tree whose root has $4$ subtrees of weight $1$. - A perfectly balanced tree whose root has $2$ subtrees of weight $2$. - A perfectly balanced tree whose root has $3$ subtrees of weight $1$. Constraints: For $33\%$ of the testdata, $N\le1000$. For another $13\%$ of the testdata, $N\le5\times 10^4$. For another $13\%$ of the testdata, $N\le10^6$. For all testdata, $1\le N\le10^9$. Translated by ChatGPT 5