#P4808. [CCC2018] 平衡树

[CCC2018] 平衡树

题目描述

题目译自 CCC 2018 S4「Balanced Trees

我们定义「完美平衡树」如下:

每棵完美平衡树都有一个正整数权值。权值为 11 的完美平衡树为只含有 11 个节点的树。否则,这棵树的权值为 w(w2)w(w\ge2),则这棵树为一棵含有 k(2kw)k(2\le k\le w) 棵子树的有根树。所有的 kk 棵子树都必须是相同的,且它的所有 kk 棵子树必须完全相同,且自身是完美平衡的。

特别地,所有 kk 棵子树权值必须相同。它们的权值必须为 wk\left\lfloor\frac{w}{k}\right\rfloor 。例如,如果一棵权值为 88 的完美平衡树有 33 棵子树,那么每棵子树的权值为 22,因为 2+2+2=682+2+2=6\le8

给定 NN,求出权值为 NN 的完美平衡树的数量。

输入格式

输入包含一行一个整数 NN

输出格式

输出一个整数表示权值为 NN 的完美平衡树的数量。

4
3
10
13

提示

样例解释 1

合法的树如下:

  • 一棵以有 44 棵权值为 11 的子树为根的完美平衡树;
  • 一棵以有 22 棵权值为 22 的子树为根的完美平衡树;
  • 一棵以有 33 棵权值为 11 的子树为根的完美平衡树。

对于 33%33\% 的数据,N1000N\le1000
对于另外 13%13\% 的数据,N5×104N\le5\times 10^4
对于另外 13%13\% 的数据,N106N\le10^6
对于全部的数据,1N1091\le N\le10^9