幽灵乐团 Sol

· · 题解

先说几句:

如果这道题有哪个神仙用单次 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 |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) 做掉了.