爱的飞行日记 题解
VinstaG173
·
·
题解
简单推式子题，预估难度弱省省选。
本文中时间复杂度 O(f^0)-O(f^1) 表示预处理复杂度 O(f^0)，单次询问复杂度 O(f^1)。
首先由 Min-max 容斥有
\operatorname{lcm}(x_1,x_2,\dots,x_n)=\prod_{S\subseteq\{1,2,\dots,n\},S \neq \varnothing}\gcd\{x_i : i \in S\}^{(-1)^{\lvert S \rvert-1}}.
事实上这个式子由 \gcd(a,b)\operatorname{lcm}(a,b) 随便算两下就出来了，不用熟知 Min-max 容斥。
由 Fibonacci 数的性质 \gcd(f_a,f_b)=f_{\gcd(a,b)}，因此
\prod_{a_1=1}^{m}\prod_{a_2=1}^{m}\cdots\prod_{a_n=1}^{m}\operatorname{lcm}(f_{a_1},f_{a_2},\dots,f_{a_n})&=\prod_{a_1=1}^{m}\prod_{a_2=1}^{m}\cdots\prod_{a_n=1}^{m}\prod_{S\subseteq\{1,2,\dots,n\},S \neq \varnothing}f_{\gcd\{a_i : i \in S\}}^{(-1)^{\lvert S \rvert-1}}\\
&=\prod_{d=1}^{m}f_d^{\sum\limits_{a_1=1}^{m}\sum\limits_{a_2=1}^{m}\cdots\sum\limits_{a_n=1}^{m}\sum\limits_{S\subseteq\{1,2,\dots,n\},S \neq \varnothing}(-1)^{\lvert S \rvert-1}[\gcd\{a_i : i \in S\}=d]}\\
&=\prod_{d=1}^{m}f_d^{\sum\limits_{k=1}^{n}(-1)^{k-1}\binom{n}{k}m^{n-k}\sum\limits_{a_1=1}^{m}\sum\limits_{a_2=1}^{m}\cdots\sum\limits_{a_k=1}^{m}[\gcd(a_1,a_2,\dots,a_k)=d]}\\
&=\prod_{d=1}^{m}f_d^{\sum\limits_{k=1}^{n}(-1)^{k-1}\binom{n}{k}m^{n-k}\sum\limits_{a_1=1}^{\left\lfloor\frac{m}{d}\right\rfloor}\sum\limits_{a_2=1}^{\left\lfloor\frac{m}{d}\right\rfloor}\cdots\sum\limits_{a_k=1}^{\left\lfloor\frac{m}{d}\right\rfloor}[\gcd(a_1,a_2,\dots,a_k)=1]}\\
&=\prod_{d=1}^{m}f_d^{\sum\limits_{k=1}^{n}(-1)^{k-1}\binom{n}{k}m^{n-k}\sum\limits_{a_1=1}^{\left\lfloor\frac{m}{d}\right\rfloor}\sum\limits_{a_2=1}^{\left\lfloor\frac{m}{d}\right\rfloor}\cdots\sum\limits_{a_k=1}^{\left\lfloor\frac{m}{d}\right\rfloor}\sum\limits_{t \mid \gcd(a_1,a_2,\dots,a_k)}\mu(t)}\\
&=\prod_{d=1}^{m}f_d^{\sum\limits_{k=1}^{n}(-1)^{k-1}\binom{n}{k}m^{n-k}\sum\limits_{t=1}^{\left\lfloor\frac{m}{d}\right\rfloor}\mu(t)\left\lfloor\frac{m}{dt}\right\rfloor^{k}}\\
&=\prod_{d=1}^{m}\prod_{t=1}^{\left\lfloor\frac{m}{d}\right\rfloor}f_d^{\mu(t)\sum\limits_{k=1}^{n}(-1)^{k-1}\binom{n}{k}m^{n-k}\left\lfloor\frac{m}{dt}\right\rfloor^{k}}\\
&=\prod_{D=1}^{m}\left(\prod_{d \mid D}f_d^{\mu\left(\frac{D}{d}\right)}\right)^{m^n-\left(m-\left\lfloor\frac{m}{D}\right\rfloor\right)^n}\\
&=\prod_{D=1}^{m}F(D)^{G\left(\left\lfloor\frac{m}{D}\right\rfloor\right)},
\end{aligned}
其中
F(D)=\prod_{d \mid D}f_d^{\mu\left(\frac{D}{d}\right)},G(k)=m^n-\left(m-k\right)^n.
直接朴素预处理 F，暴力计算可以做到时间复杂度 O(m\log m)-O(m\log n)。
为了优化，可以用整除分块处理上式。我们可以在 O(\log{n}) 的时间复杂度下计算 G(\cdot)，现在我们考虑较快速计算 F(D)。
由于
\prod_{i=1}^{D}F(i)=\prod_{d=1}^{D}f_d^{\sum\limits_{i=1}^{\left\lfloor\frac{D}{d}\right\rfloor}\mu(i)},
我们可以线性预处理 Fibonacci 数列前缀积和 \mu(\cdot) 前缀和后用整除分块在 O(\sqrt{D}\log{D}) 的时间复杂度下计算上式。时间复杂度 O(m)-O(m^{\frac{3}{4}}\log{n})。
注意到模数不大，线性预处理出逆元，利用类似 Dirichlet 前缀和的方法计算卷积预处理出 F(\cdot)，同时用 Euler 定理优化计算 k^n，即可做到 O(mod+m\log{\log{m}})-O(\sqrt{m}\log{mod})，空间复杂度 O(mod+m)。
以上做法已经足够通过本题，但其实不考虑多组询问我们还可以做到更优。以下做法由验题人 wkywkywky 提出。
注意刚才的式子
\prod_{i=1}^{D}F(i)=\prod_{d=1}^{D}f_d^{\sum\limits_{i=1}^{\left\lfloor\frac{D}{d}\right\rfloor}\mu(i)},
我们只需要求出 F,f 与 \mu 的块筛。其中 \mu 函数前缀和可以用杜教筛做到 O(v)-O(\frac{m}{\sqrt{v}})，f 数列前缀积可以用这道题的方法，O(V+W\log W) 预处理，且对于 m/i>V，做到 O(m/W) 单次查询。
在处理出 f 和 \mu 的基础上，预处理 F 的前缀积到 O(w)，可以做到 O(w\log\log w\log mod)-O(\frac m{\sqrt w}\log mod)。平衡复杂度取 v,V,w=O((m\operatorname{polylog})^{2/3})，总复杂度约为 O((m\operatorname{polylog})^{2/3})，可能常数较大，瓶颈主要在 F 的计算过程中的 \log mod，\mu,f,F 三部分的 \log 次数大约分别为 0,\frac13,1^+。