统计满足元素可被其1起始下标整除的数组子序列总数

常规O(n²)的解法基于动态规划实现：定义dp[k]表示长度恰好为k的满足条件的子序列总数，初始状态dp[0] = 1对应空序列。遍历数组中的每个元素x时，从当前最大可能的子序列长度倒序遍历到1，若x能被k整除则执行dp[k] += dp[k-1]，最终dp[1...n]的和即为答案。该方法在n超过1e3之后性能会明显下降。

O(n*√maxA) 优化方案 #

我们可以通过枚举约数的方式大幅减少无效遍历，把时间复杂度降到可处理1e5级数据的水平：
核心逻辑很简单：只有当k是x的约数时，x才能放在长度为k的子序列的最后一位，所以不需要遍历所有可能的k值，只需要枚举x的所有约数即可。
具体实现步骤：

• 初始化dp数组，dp[0] = 1，其余位置初始为0
• 遍历数组中的每个元素x：
  1. 枚举x的所有正约数，只保留小于等于n的约数（子序列长度不可能超过数组总长度n）
  2. 将筛选出的约数按照从大到小排序，避免更新时状态重复计算
  3. 对每个约数k，执行dp[k] += dp[k-1]
• 最终统计dp[1]到dp[n]的和就是答案

由于每个正整数的约数个数最多为O(√x)，实际场景中大多数数的约数个数不超过200，整体复杂度远低于O(n²)。拿你给出的示例验证：
输入数组[2,2,1,22,14]，处理第一个元素2时，它的约数为1、2，倒序处理后：
dp[2] += dp[1]（初始dp[1]为0无变化），dp[1] += dp[0]，dp[1]变为1，和预期逻辑一致，最终求和结果正好是13。

内容的提问来源于stack exchange，提问作者Emma Funkhouser