幽灵乐团 Sol

CYJian

2019-08-15 21:41:09

Solution

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