本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-10-08 20:13:36

考虑到如果是整个区间怎么做。设 $f_i$ 表示以 $i$ 为结尾的合法子序列数量。那么

$$ f_i = 1 + \sum\limits_{j\lt i, a_j\mid a_i} f_j $$

考虑可以扫描线。固定左端点，从后往前，考虑 $i$ 作为左端点对于后面的贡献。那么，所有是 $a_i$ 的的倍数的 $\rg a_i\mid a_j$，都可以使得 $f_j$ 加上 $1$。同时，可以间接转移，也就是使得 $a_i\mid a_j\mid a_k$ 的 $f_k$ 上头加上 $f_j$。

我们这么样就做完了。