题解

思路推导

设 $dp_j$ 表示处理完当前前缀后，长度恰为 $j$ 的好子序列数量。考虑新元素 $x$：若 $j\mid x$，就可以把 $x$ 接到任意长度为 $j-1$ 的好子序列之后，得到长度为 $j$ 的新子序列，因此有

初始令 $dp_0=1$，表示空前缀，便可统一产生长度为一的子序列。更新长度必须从大到小，避免同一个数组元素在一次处理中被重复选取。

直接枚举所有 $j$ 需要二次时间。只有 $x$ 的约数才可能满足转移，因此对每个元素枚举不超过 $n$ 的约数，并按降序更新即可。

做法

依次处理数组元素。枚举 $x$ 的所有因数对，把不超过 $n$ 的因数收集起来，降序执行状态转移。最终答案是 $dp_1+dp_2+\cdots+dp_n$。

小规模可以枚举所有非空下标集合；中等规模可以对每个元素从当前最大可能长度向下检查整除关系。独立核验程序还可用筛法预处理每个值对应的不超过 $n$ 的约数表。

正确性证明

处理元素 $x$ 时，每个以 $x$ 作为最后一个元素、长度为 $j$ 的新好子序列，都唯一来自一个此前长度为 $j-1$ 的好子序列，且存在的充要条件是 $j\mid x$。转移恰好为这些前缀各追加一次 $x$，因此不漏不重。

降序更新保证右侧的 $dp_{j-1}$ 尚未包含当前元素，所以每个下标最多被选一次。归纳可知，处理任意前缀后 $dp_j$ 都准确统计该前缀内长度为 $j$ 的好子序列。最后对所有非空长度求和即得到答案。

复杂度分析

对每个元素用 $O(\sqrt{a_i})$ 时间枚举约数，总时间复杂度为 $O(\sum\sqrt{a_i})$，空间复杂度为 $O(n)$。