爱的飞行日记题解

简单推式子题，预估难度弱省省选。

本文中时间复杂度

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$ 数列前缀积可以用[这道题](https://www.luogu.com.cn/problem/AT_abc381_g)的方法，$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^+$。

爱的飞行日记题解

文章操作

相关推荐

评论

爱的飞行日记题解