关于模考 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]
2