题解

思路

固定末项 $A_N=x$，把 $x$ 分解为 $\prod p^{e_p}$。

做法

整除关系等价于每个质因子的指数在序列中单调不减；对于某个指数 $e$，从 $0$ 开始在 $N-1$ 次转移中安排总计 $e$ 次增加，方案数是 $\binom{N+e-1}{e}$。不同质因子彼此独立，因此末项为 $x$ 的方案数为 $\prod_{p^{e_p}\mid x}\binom{N+e_p-1}{e_p}$，再对 $1\le x\le M$ 求和即可。用阶乘和逆阶乘预处理组合数，并用最小质因子筛分解每个 $x$；每一种合法序列按其末项唯一计入，反之每组非降指数也唯一确定一条合法序列，所以计数不重不漏。

复杂度

总时间复杂度为 $O(N+M\log M)$，空间复杂度为 $O(N+M)$。