Canadian Computing Competition: 2018 Stage 1, Senior #4
Trees have many fascinating properties. While this is primarily true for trees in nature, the concept of trees in math and computer science is also interesting. A particular kind of tree, a perfectly balanced tree, is defined as follows.
Every perfectly balanced tree has a positive integer weight. A perfectly balanced tree of weight ~1~ always consists of a single node. Otherwise, if the weight of a perfectly balanced tree is ~w~ and ~w \ge 2~, then the tree consists of a root node with branches to ~k~ subtrees, such that ~2 \le k \le w~. In this case, all ~k~ subtrees must be completely identical, and be perfectly balanced themselves.
In particular, all ~k~ subtrees must have the same weight. This common weight must be the maximum integer value such that the sum of the weights of all ~k~ subtrees does not exceed ~w~, the weight of the overall tree. For example, if a perfectly balanced tree of weight ~8~ has ~3~ subtrees, then each subtree would have weight ~2~, since ~2 + 2 + 2 = 6 \le 8~.
Given ~N~, find the number of perfectly balanced trees with weight ~N~.
The input will be a single line containing the integer ~N~ ~(1 \le N \le 10^9)~.
For ~5~ of the ~15~ marks available, ~N \le 1\,000~.
For an additional ~2~ of the ~15~ marks available, ~N \le 50\,000~.
For an additional ~2~ of the ~15~ marks available, ~N \le 10^6~.
Output a single integer, the number of perfectly balanced trees with weight ~N~.
Sample Input 1
Sample Output 1
Explanation for Sample Output 1
One tree has a root with four subtrees of weight ~1~; a second tree has a root with two subtrees of weight ~2~; the third tree has a root with three subtrees of weight ~1~.
Sample Input 2
Sample Output 2