关于 Good arrays

· · 算法·理论

本来是想要提交到娱乐的，可是提交不了了。

题目

Good arrays。

我的解法

这道题目的时间限制为 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}

那么，我们使用插板法即可得到：

\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，都有 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 代表非负整数集。

它有一个性质：

还有一些性质，就不一一列举了，我们的证明中用到了如上两个性质。