带因子的二叉树

记住这句口诀：排序、dp 从 1 起步、枚举因子对、乘法原理累加、最后求和。后面每一帧都在套它。

第一步先排序：2, 4, 5, 10。排序是为了保证算到 x 时，比它小的因子都已经算好 dp 了。右边面板就是 dp 表，现在每个值都是 1。

dp[x] 为什么从 1 起步？因为任何一个数单独拎出来就是一棵只有根的合法树。这 4 个 1，就是示例 7 棵里最朴素的 4 棵。

强调一下顺序：因子 b、c 都严格小于它们的乘积 x，排序后它们一定排在 x 前面、dp 已经算好。所以从左往右一个个算，永远能拿到现成的因子 dp。

先看最小的 2。它要拆成两个因子相乘，最小也得是别的数当孩子，但没有比它更小的数在表里，所以 2 只能是单结点，dp[2] 保持 1。

轮到 4。先把它自己当单结点那 1 棵记上，dp[4] 从 1 起步。接着去前面找：有没有两个数相乘正好等于 4，能当它的左右孩子。

试因子 2：4 能被 2 整除，商是 2，而 2 也在表里。这就凑成一对合法孩子，左孩子 2、右孩子 2 相乘正好 4。

用乘法原理：左子树有 dp[2] = 1 种长法，右子树有 dp[2] = 1 种，自由组合就是 1 × 1 = 1 种，累加进 dp[4]，现在是 2。

4 的因子对枚举完了，dp[4] 最终是 2：单结点 1 棵，加上各因子对带来的组合。

轮到 5。先把它自己当单结点那 1 棵记上，dp[5] 从 1 起步。接着去前面找：有没有两个数相乘正好等于 5，能当它的左右孩子。

试因子 2：5 除以 2 除不尽，2 根本不是 5 的因子，当不了它的孩子，跳过。

试因子 4：5 除以 4 除不尽，4 根本不是 5 的因子，当不了它的孩子，跳过。

5 前面的数都没法两两相乘等于它，所以它只有单结点这一种，dp[5] 锁定为 1。

轮到 10。先把它自己当单结点那 1 棵记上，dp[10] 从 1 起步。接着去前面找：有没有两个数相乘正好等于 10，能当它的左右孩子。

试因子 2：10 能被 2 整除，商是 5，而 5 也在表里。这就凑成一对合法孩子，左孩子 2、右孩子 5 相乘正好 10。

用乘法原理：左子树有 dp[2] = 1 种长法，右子树有 dp[5] = 1 种，自由组合就是 1 × 1 = 1 种，累加进 dp[10]，现在是 2。

试因子 4：10 除以 4 除不尽，4 根本不是 10 的因子，当不了它的孩子，跳过。

试因子 5：10 能被 5 整除，商是 2，而 2 也在表里。这就凑成一对合法孩子，左孩子 5、右孩子 2 相乘正好 10。

用乘法原理：左子树有 dp[5] = 1 种长法，右子树有 dp[2] = 1 种，自由组合就是 1 × 1 = 1 种，累加进 dp[10]，现在是 3。

10 的因子对枚举完了，dp[10] 最终是 3：单结点 1 棵，加上各因子对带来的组合。

四个 dp 都算好了：2 是 1 棵，4 是 2 棵，5 是 1 棵，10 是 3 棵。每个数当根能搭多少树，面板里一目了然。

每个数都可以当整棵树的根，所以答案是把所有 dp 加起来：1 + 2 + 1 + 3 = 7。

于是 arr = [2, 4, 5, 10] 一共能搭出 7 棵合法二叉树，和示例对上了。数据大时记得每步对 1e9+7 取余。

边界先想清：单个数、两个互质数、全质数，这些都搭不出非叶结点，答案就是元素个数。

面试重点：讲清「枚举因子天然覆盖左右对称」和「哈希表加速判断因子是否存在」两点。