自动搬运

查看原文

来自洛谷，原作者为

	CYJian 今日はこっちの地方はどしゃぶりの晴天でした，昨日もずっと暇で一日満喫してました

搬运于2025-08-24 22:11:37，当前版本为作者最后更新于2019-08-15 21:41:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

先说几句:

如果这道题有哪个神仙用单次 $O(n\log n)$ 的复杂度过了我请您抽烟。

欢迎大佬吊打垃圾标算。

本片题解中有部分地方由于人懒所以复制粘贴的时候 $td$ 没有换成 $T$, 请各位大佬自行替换一下吧（有时间再补锅）。

---

首先对于 $10$ 分的数据可以直接暴力求。

然后如果打出一张 $\gcd$ 的表，然后 $n^3$ 模拟预处理就可以获得 $30$ 分。

首先，我们注意到原式可以化为下面这样：

$$\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} \left(\frac{{\rm lcm}(i,j)}{\gcd(i,k)}\right)^{f(type)} $$$$\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} \left(\frac{i\times j}{\gcd(i,j)\times \gcd(i,k)}\right)^{f(type)} $$

然后，显然可以分为两个子问题：

$$\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} i^{f(type)} $$$$\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} gcd(i,j)^{f(type)} $$

然后我们就根据 type 分别推一推式子吧。

${\rm type=0}$

我们先来看看第一个式子吧：

$$\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} i$$ $$\prod_{i=1}^{A}\prod_{j=1}^{B} i^{C}$$ $$\left(\prod_{i=1}^{A}i\right)^{B \times C}$$

预处理一个阶乘，写个快速幂就完事了。

然后就是第二个式子了。

$$\left(\prod_{i=1}^{A}\prod_{j=1}^{B} gcd(i,j)\right)^{C} $$

然后这就可以过$10^3$了。然后就可以得到12分了。

然后就可以反演了。

如果不会莫比乌斯反演，那么就请先科普完莫比乌斯反演并且推了几道题后再来看这篇题解。

然后继续吧。

$$\left(\prod_{i=1}^{A}\prod_{j=1}^{B} \gcd(i,j)\right)^{C} $$$$\left(\prod_{d=1}d^{\sum_{i=1}^{A/d}\sum_{j=1}^{B/d} [\gcd(i,j)=1]}\right)^{C} $$$$\left(\prod_{d=1}d^{\sum_{t=1}\mu(t)\left\lfloor\frac{A}{td}\right\rfloor\left\lfloor\frac{B}{td}\right\rfloor}\right)^{C} $$$$\left(\prod_{T=1}\left(\prod_{d|T}d^{\mu(\frac{T}{d})}\right)^{\left\lfloor\frac{A}{td}\right\rfloor\left\lfloor\frac{B}{td}\right\rfloor}\right)^{C} $$

显然中间的式子可以像狄利克雷卷积一样 $O(n\log n)$ 预处理出来，然后整除分块可以 $O(\sqrt{n}\log n)$ 做掉。

这两个式子结合一下就有 $20$ 分了。

${\rm type=1}$

一样,我们先来考虑第一个式子。

$$\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} i^{i \times j \times k} $$$$\prod_{i=1}^{A}\prod_{j=1}^{B} i^{i \times j \times \sum_{k=1}^{C}k} $$$$\prod_{i=1}^{A} i^{i \times (\sum_{j=1}^{B}j) \times (\sum_{k=1}^{C}k)} $$$$\left(\prod_{i=1}^{A} i^i\right)^{F(B) \times F(C)} $$

其中: $F(x)=\frac{x \times (x + 1)}{2}$。

这个东西可以 $O(n\log n)$ 预处理一下, 再加上快速幂就行了。

记得指数上要对 $mod-1$ 取模。

然后考虑第二个式子。

$$\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} gcd(i,j)^{i \times j \times k} $$$$\left(\prod_{i=1}^{A}\prod_{j=1}^{B} gcd(i,j)^{i \times j}\right)^{F(C)} $$

这里就能做 $n \leq 10^3$ 的数据了。

大概用 $O(n^2\log n)$ 的时间打一个 $n^2$ 的表，然后预处理矩阵的前缀积，询问直接 $O(1)$ 查表后加上一个 $F(C)$ 的快速幂就行了。

然后继续推:

$$\left(\prod_{d=1}d^{d^2\sum_{i=1}^{A/d}\sum_{j=1}^{B/d} i \times j \times [gcd(i, j)=1]}\right)^{F(C)} $$$$\left(\prod_{d=1}d^{\sum_{t=1}d^2\mu(t)t^2F(\left\lfloor\frac{A}{td}\right\rfloor)F(\left\lfloor\frac{B}{td}\right\rfloor)}\right)^{F(C)} $$$$\left(\prod_{T=1}\left( \left(\prod_{d|T} d^{\mu(\frac{T}{d})}\right)^{T^2} \right)^{F(\left\lfloor\frac{A}{td}\right\rfloor)F(\left\lfloor\frac{B}{td}\right\rfloor)}\right)^{F(C)} $$

虽然式子看上去麻烦了一点，但是还是能预处理的。

中间那一坨 $\left(\prod_{d|T} d^{\mu(\frac{T}{d})}\right)^{T^2}$ 可以用类似狄利克雷卷积的办法预处理，复杂度还是 $O(n \log n)$。

然后预处理一个前缀积以及逆元啥的就能单次询问 $O(\sqrt{n} \log n)$ 了。

结合以上的所有算法，可以得到 $60$ 分。

${\rm type=2}$

还是先康康第一个式子:

$$\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} i^{\gcd(i,j,k)} $$

考虑反演:

$$\prod_{d=1}\prod_{i=1}^{A/d}(id)^{d\sum_{j=1}^{B/d}\sum_{k=1}^{C/d}[\gcd(i,j,k)=1]} $$$$\prod_{d=1}\prod_{t=1}\prod_{i=1}^{A/td}(itd)^{\mu(t)d \left\lfloor\frac{B}{td}\right\rfloor\left\lfloor\frac{C}{td}\right\rfloor} $$$$\prod_{T=1}\left(\prod_{d|T}\left(fac\left(\left\lfloor\frac{A}{T}\right\rfloor\right) \times T^{\left\lfloor\frac{A}{T}\right\rfloor}\right)^{\mu(\frac{T}{d})d }\right)^{\left\lfloor\frac{B}{T}\right\rfloor\left\lfloor\frac{C}{T}\right\rfloor} $$$$\prod_{T=1}\left(\left(fac\left(\left\lfloor\frac{A}{T}\right\rfloor\right) \times T^{\left\lfloor\frac{A}{T}\right\rfloor}\right)^{\sum_{d|T}\mu(\frac{T}{d})d }\right)^{\left\lfloor\frac{B}{T}\right\rfloor\left\lfloor\frac{C}{T}\right\rfloor} $$$$\prod_{T=1}\left(\left(fac\left(\left\lfloor\frac{A}{T}\right\rfloor\right) \times T^{\left\lfloor\frac{A}{T}\right\rfloor}\right)^{\varphi(T)}\right)^{\left\lfloor\frac{B}{T}\right\rfloor\left\lfloor\frac{C}{T}\right\rfloor} $$

然后对于 $T^{\varphi(T)}$ 做个前缀积以及逆元的预处理就行了...再预处理一个模$mod-1$ 意义下的 $\varphi(T)$ 的前缀和, 做整除分块的时候 $\frac{A}{T}$ 的指数.

然后考虑第二个式子.

我们考虑枚举 $\gcd(i,j)$

$$\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} \gcd(i,j)^{\gcd(i,j,k)} $$$$\prod_{d=1}d^{\sum_{i=1}^{A/d}\sum_{j=1}^{B/d}[gcd(i,j)=1] \times \sum_{k=1}^{C} \gcd(d,k)} $$$$\prod_{d=1}d^{\left(\sum_{t=1}\mu(t)\left\lfloor\frac{A}{td}\right\rfloor\left\lfloor\frac{B}{td}\right\rfloor\right) \times \left(\sum_{k=1}^{C} \gcd(d,k)\right)} $$$$\prod_{T=1}\left(\prod_{d|T}d^{\mu(\frac{T}{d}) \times \left(\sum_{k=1}^{C} \gcd(d,k)\right)}\right)^{\left\lfloor\frac{A}{T}\right\rfloor\left\lfloor\frac{B}{T}\right\rfloor} $$

把里面那个 $\gcd$ 的式子拿出来:

$$\sum_{k=1}^{C} gcd(d,k)$$ $$\sum_{d'|d}d'\sum_{k=1}^{C/d'} [gcd(\frac{d}{d'},k) = 1] $$$$\sum_{d'|d}d'\sum_{t'|\frac{d}{d'}}\mu(t')\left\lfloor\frac{C}{t'd'}\right\rfloor $$$$\sum_{T' |d}\left\lfloor\frac{C}{T'}\right\rfloor\varphi(T')$$

然后套回去。

这样大概能拿个$n \leq 1000$的分数。

其实..我们如果把它套回到前一个式子里头:

$$\prod_{d=1}d^{\left(\sum_{t=1}\mu(t)\left\lfloor\frac{A}{td}\right\rfloor\left\lfloor\frac{B}{td}\right\rfloor\right) \times \left(\sum_{T'|d}\left\lfloor\frac{C}{T'}\right\rfloor\varphi(T')\right)} $$

你会发现,它可以用 $O(n \log n)$ 的时间复杂度完成。

如果你常数优化很牛逼，过了我请你抽烟

当然还有另外一种做法: 枚举 $\gcd(i,j,k)$。

$$\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} \gcd(i,j)^{\gcd(i,j,k)} $$$$\prod_{d=1}\prod_{i=1}^{A/d}\prod_{j=1}^{B/d} (d \times \gcd(i,j))^{d\sum_{k=1}^{C/d}[\gcd(i,j,k)=1]} $$$$\prod_{d=1}\prod_{t=1}\prod_{i=1}^{A/td}\prod_{j=1}^{B/td} (td \times \gcd(i,j))^{\mu(t)d\left\lfloor\frac{C}{td}\right\rfloor} $$

然后我们把底数的td分离出来:

$$\left(\prod_{d=1}\prod_{t=1}(td)^{\mu(t)d\left\lfloor\frac{A}{td}\right\rfloor\left\lfloor\frac{B}{td}\right\rfloor\left\lfloor\frac{C}{td}\right\rfloor}\right) \times \left(\prod_{d=1}\prod_{t=1}\prod_{i=1}^{A/td}\prod_{j=1}^{B/td} \gcd(i,j)^{\mu(t)d\left\lfloor\frac{C}{td}\right\rfloor}\right) $$

然后把前面一坨式子拿出来:

$$\prod_{d=1}\prod_{t=1}(td)^{\mu(t)d\left\lfloor\frac{A}{td}\right\rfloor\left\lfloor\frac{B}{td}\right\rfloor\left\lfloor\frac{C}{td}\right\rfloor} $$$$\prod_{T=1}T^{\left\lfloor\frac{A}{td}\right\rfloor\left\lfloor\frac{B}{td}\right\rfloor\left\lfloor\frac{C}{td}\right\rfloor\sum_{d|T}\mu(\frac{T}{d})d} $$$$\prod_{T=1}(T^{\varphi(T)})^{\left\lfloor\frac{A}{td}\right\rfloor\left\lfloor\frac{B}{td}\right\rfloor\left\lfloor\frac{C}{td}\right\rfloor} $$

然后我们拿出前面 $i^{gcd(i,j,k)}$ 的部分:

$$\prod_{T=1}\left(\left(fac\left(\left\lfloor\frac{A}{T}\right\rfloor\right) \times T^{\left\lfloor\frac{A}{T}\right\rfloor}\right)^{\varphi(T)}\right)^{\left\lfloor\frac{B}{T}\right\rfloor\left\lfloor\frac{C}{T}\right\rfloor} $$

也把底数拿出来:

$$\left(\prod_{T=1}\left(fac\left(\left\lfloor\frac{A}{T}\right\rfloor\right)\right)^{\varphi(T)\left\lfloor\frac{B}{T}\right\rfloor\left\lfloor\frac{C}{T}\right\rfloor}\right) \times \left(\prod_{T=1}\left(T^{\varphi(T)}\right)^{\left\lfloor\frac{A}{T}\right\rfloor\left\lfloor\frac{B}{T}\right\rfloor\left\lfloor\frac{C}{T}\right\rfloor}\right) $$

然后发现后面一坨东西是可以约掉的。然后我们就变成了分别计算下面两个部分:

$$\prod_{T=1}\left(fac\left(\left\lfloor\frac{A}{T}\right\rfloor\right)\right)^{\varphi(T)\left\lfloor\frac{B}{T}\right\rfloor\left\lfloor\frac{C}{T}\right\rfloor} $$$$\prod_{d=1}\prod_{t=1}\prod_{i=1}^{A/td}\prod_{j=1}^{B/td} \gcd(i,j)^{\mu(t)d\left\lfloor\frac{C}{td}\right\rfloor} $$

显然第一个式子已经可以整除分块做了。

但是第二个还需要再搞搞。

$$\prod_{d=1}\prod_{t=1}\prod_{d'=1}\prod_{t'=1} d'^{\mu(t')\mu(t)d\left\lfloor\frac{C}{td}\right\rfloor\left\lfloor\frac{A}{tt'dd'}\right\rfloor\left\lfloor\frac{B}{tt'dd'}\right\rfloor} $$$$\prod_{T=1}\left(\prod_{T'=1} \left(\prod_{d|T'}d^{\mu(\frac{T'}{d})}\right)^{\left\lfloor\frac{A}{TT'}\right\rfloor\left\lfloor\frac{B}{TT'}\right\rfloor}\right)^{\varphi(T)\left\lfloor\frac{C}{T}\right\rfloor} $$

预处理出中间那一坨 $\prod_{d|T'}d^{\mu(\frac{T'}{d})}$ 之后, 可以两次整除分块 $O(n^{0.75} \log n)$ 做掉了.