今天做到模考的 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 3
Output 1
7
Input 2
2 6
Output 2
14
样例解释
对于第一个数填 1\sim 6，分别有 [6,3,2,1,1,1] 种第二个数，故总共有 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<n) 且 1\le b_1\le \left \lfloor \frac{c}{k}\right \rfloor 。
那么，由于 b_n=1，我们只需要考虑剩下 n-1 个数即可，易见 b_1 为 b 数列中其它所有数的倍数，我们不妨考虑，将 b_n 分解为 n-1 个数的乘积。
我们假设 \mathrm{f}(x) 代表将 x 分解为 n-1 个数的乘积的方案数。
那么，我们简化后的问题的答案就为：
$$\sum_{i=1}^{\left \lfloor \frac{c}{k} \right \rfloor }\mathrm{f}(i)$$
然后，由于我们上面的 k 的范围为 1\le k\le c，所以最后的答案就是：
$$\sum_{i=1}^{c}\sum_{j=1}^{\left \lfloor \frac{c}{i} \right \rfloor }\mathrm{f}(j)$$
那么问题就变成了，用线性复杂度求出 \mathrm{f}(x) 的大小，把这个问题解决了，其它就都好办了。
我们考虑分解 x：
$$x=\prod_{i=1}^{m}p_i^{\alpha_i}$$
那么，我们使用插板法即可得到：
$$\mathrm{f}(x)=\prod_{j}\begin{pmatrix}
\alpha_j+n-2 \n-2
\end{pmatrix}$$
然后，我们应该时可以证明 \mathrm{f}(x) 为积性函数的。
具体的，我们需要证明当 \gcd(a,b)=1 时，\mathrm{f}(a\times b)=\mathrm{f}(a)\times \mathrm{f}(b)。
我们考虑 \mathrm{f}(a\times b) 这个函数的值为 \prod_{i=1}^{n-1}c_i=a\times b 的 k 元组 (c_1,c_2,\dots,c_{n-1}) 的数量。
由于 \gcd(a,b)=1 所以我们可以唯一分解 c_i=d_i\times e_i，并且 d_i\mid a,e_i\mid b 且 \gcd(d_i,e_i)=1，则：
$$\prod_{i=1}^{n-1}c_i=\prod_{i=1}^{n-1}(d_i\times e_i)=\left(\prod_{i=1}^{n-1}d_i\right)\times \left(\prod_{i=1}^{n-1}e_i\right)=a\times b$$
接下来，我们只需要证明 \prod_{i=1}^{n-1}d_i=a,\prod_{i=1}^{n-1}e_i=b 即可。
我们取任意质数 p：
- 若 p\mid a，则 p\nmid b，此时 v_p(a\times b)=v_p(a)+v_p(b)=v_p(a)，又因为 v_p(c_i)=v_p(d_i)+v_p(e_i)，但是 e_i\mid b 所以 v_p(e_i)=0，所以 v_p(c_i)=v_p(d_i)，因此：
$$v_p\left(\prod_{i=1}^{n-1}d_i\right)=\sum_{i=1}^{n-1}v_p(d_i)=\sum_{i=1}^{n-1}v_p(c_i)=v_p(ab)=v_p(a)$$ - 若 p\mid b，与上面同理可得 v_p\left(\prod_{i=1}^{n-1}e_i\right)=v_p(b)。
- 若 p\nmid a\times b，那么 v_p\left(\prod_{i=1}^{n-1}d_i\right)=0=v_p(a),v_p\left(\prod_{i=1}^{n-1}e_i\right)=0=v_p(b)。
所以，对于所有的质数 p，都有 v_p\left(\prod_{i=1}^{n-1}d_i\right)=v_p(a) 和 v_p\left(\prod_{i=1}^{n-1}e_i\right)=v_p(b)，所以 \prod_{i=1}^{n-1}d_i=a,\prod_{i=1}^{n-1}e_i=b。
然后，这道题目就好做了，我们考虑使用线性筛求 \mathrm{f}(x)，我们考虑两种情况当前的数为 i，质数为 p_i。
若 p_i\mid i，则我们推一下式子，就是我们设 i=p_i^k\times m 那么现在的 i\times p_i=p_i^{k+1}\times m，我们用我们上面的表达式写出来，也就是 \mathrm{f}(i)=\begin{pmatrix}k+n-2\\n-2\end{pmatrix}\times \mathrm{g}_{m},\mathrm{f}(i\times p_i)=\begin{pmatrix}k+n-1\\n-2\end{pmatrix}\times \mathrm{g}_{m}，我们那么我们将这两个式子做比，就能得到：
$$\frac{\mathrm{f}(i\times p_i)}{\mathrm{f}(i)}=\frac{\begin{pmatrix}k+n-1\n-2\end{pmatrix}}{\begin{pmatrix}k+n-2\n-2\end{pmatrix}}=\frac{k+n-1}{k+1}$$
所以，我们可以得到 \mathrm{f}(i\times p_i)=\mathrm{f}(i)\times\frac{k+n-1}{k+1}，这里我们用乘法逆元做就可以了。
第二种情况就是，若 p_i\mid i 那么，由于 \mathrm{f}(x) 为积性函数，所以 \mathrm{f}(i\times p_i)=\mathrm{f}(i)\times \mathrm{f}(p_i)。
然后，这道题目就基本做完了，我们只需要再加一点细节就够了。
关于积性函数证明中的解释
我们的证明过程中出现了一种符号，叫做 p 进赋值，它的定义为 v_p(x)=\max\left\{k\in \mathbb{N}_0\ |\ p^k\mid x \right\}，其中 \mathbb{N}_0 代表非负整数集。
它有一个性质：
- 若 p\nmid x，则 v_p(x)=0。
- 对于任意正整数 a,b 和质数 p 有 v_p(a\times b)=v_p(a)+v_p(b)。
还有一些性质，就不一一列举了，我们的证明中用到了如上两个性质。
后记
这模考 T2 咋还是原题呀：link。
其实这道题目不证明积性函数也能做，主要由 wzr 巨佬提供，原因是在和 wzr 讨论这道题目的时候，wzr 说这个函数绝对不是积性函数，于是不用积性函数做出了这道题目。不过这道题目怎么还卡空间呢？
不过也有可能是作者错了，如有错误，请指出。