关于模考 T2
今天做到模考的 T2，太有意思了。题目描述
最近，Bob 学习了整数除法。受到这一神圣知识的启发，他决定进一步了解满足某些整除条件的正整数数组。具体来说，Bob 将一个数组 \(a=a_1,a_2,\dots,a_n\) 称为"好数组"，当且仅当对于每个 \(i\)（从 \(1\) 到 \(n-1\)），\(a_i\) 能被 \(a_{i+1}\) 整除。请帮助他计算长度为 \(n\) 且所有元素不超过 \(c\) 的好数组的数量。
输入格式
输入只有一行，包含两个整数 \(n\) 和 \(c\)——数组的长度和允许的最大值。
输出格式
输出一个整数——长度为 \(n\) 且所有元素为不超过 \(c\) 的正整数的好数组的总数。由于这个数可能非常大，请输出其对 \(998244353\) 取模的结果。
样例
Input 1
3 3Output 1
7Input 2
2 6Output 2
14样例解释
对于第一个数填 \(1\sim 6\)，分别有 \(\) 种第二个数，故总共有 \(14\) 种。
数据范围
对于 \(10\%\) 的数据满足：\(1\le n,c\le 10\)。
对于 \(50\%\) 的数据满足：\(1\le n,c\le 10^5\)。
对于 \(100\%\) 的数据满足：\(1\le n,c\le 5\times 10^7\)。
我的解法
这道题目的时间限制为 \(2\) 秒，空间限制为 \(1048576\ \mathrm{kB}\)。
注意数据范围，可知我们需要一个线性复杂度。
我们可以设 \(a_n=k\)，那么我们就有 \(k\mid a_i\ (1\le k\le n)\)，那我们不妨得到一个新的数列 \(b\) 使得 \(b_i=\frac{a_i}{k}\)。
那么原本的问题就转化为了 \(b_n=1\) 且 \(b_{i+1}\mid b_i\ (1\le i
页:
[1]