https://www.luogu.com.cn/training/168096
CF1359E
Lemma:
\(\forall x\in \mathbb{N},\ x \bmod a \bmod b=x \bmod b \bmod a \iff a\mid b\ (a<b)\)
Proof:
因为 \(a<b\)，所以 \(x \bmod a \bmod b=x \bmod a\)。
设 \(x=pb+q\)，其中 \(0<q<b\)。
则原式等价于 \(\forall x\in \mathbb{N},\ pb+q\equiv q\pmod a\)。
由 \(x\) 的任意性，令 \(p=1\)，得 \(a\mid b\)。
另一方面，当 \(a\mid b\) 时，\(x\) 模 \(b\) 后会减去一个 \(b\) 的倍数，而这个数也是 \(a\) 的倍数，故不改变模 \(a\) 的结果。
回到此题。
\(\forall j=2,3...n\)，有 \(x \bmod {a_1} \bmod{a_j} \bmod \cdots=x \bmod{a_j} \bmod {a_1} \bmod \cdots\)，则 \(a_1\mid a_j\)。
因此序列中所有数都是 \(a_1\) 的倍数。
另一方面，由 Lemma 证明最后一行，不难发现此时满足限制。
最后的计数是显然的。
枚举 \(a_1\) 的值 \(m\)，则此时方案为 \(\binom{\lfloor {\frac{n}{m}} \rfloor -1}{k-1}\)，求和即为答案。