幽灵乐团 Sol
先说几句:
如果这道题有哪个神仙用单次O(n\log n)O(nlogn)的复杂度过了, 我请您抽烟
欢迎大佬dd垃圾标算
本片题解中有部分地方由于人懒所以复制粘贴的时候tdtd没有换成TT, 请各位大佬自行替换一下吧(有时间再补锅)
首先对于 1010 分的数据可以直接暴力求。
然后如果打出一张 gcdgcd 的表，然后 n^3n3 模拟预处理就可以获得 3030 分。
首先，我们注意到原式可以化为下面这样：
\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} \left(\frac{lcm(i,j)}{gcd(i,k)}\right)^{f(type)}i=1∏A?j=1∏B?k=1∏C?(gcd(i,k)lcm(i,j)?)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)}i=1∏A?j=1∏B?k=1∏C?(gcd(i,j)×gcd(i,k)i×j?)f(type)
然后，显然可以分为两个子问题：
\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} i^{f(type)}i=1∏A?j=1∏B?k=1∏C?if(type)
\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} gcd(i,j)^{f(type)}i=1∏A?j=1∏B?k=1∏C?gcd(i,j)f(type)
然后我们就根据 typetype 分别推一推式子吧=-=
{\rm type=0}type=0
我们先来看看第一个式子吧：
\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C} ii=1∏A?j=1∏B?k=1∏C?i
\prod_{i=1}^{A}\prod_{j=1}^{B} i^{C}i=1∏A?j=1∏B?iC
\left(\prod_{i=1}^{A}i\right)^{B \times C}(i=1∏A?i)B×C
预处理一个阶乘，写个快速幂就完事了=-=
然后就是第二个式子了。
\left(\prod_{i=1}^{A}\prod_{j=1}^{B} gcd(i,j)\right)^{C}(i=1∏A?j=1∏B?gcd(i,j))C
然后这就可以过10^3103了。。然后就可以得到12分了=-=
然后就可以反演了=-=
如果不会莫比乌斯反演，那么就请先科普完莫比乌斯反演并且推了几道题后再来看这篇题解。
然后继续吧。
\left(\prod_{i=1}^{A}\prod_{j=1}^{B} gcd(i,j)\right)^{C}(i=1∏A?j=1∏B?gcd(i,j))C
\left(\prod_{d=1}d^{\sum_{i=1}^{A/d}\sum_{j=1}^{B/d} [gcd(i,j)=1]}\right)^{C}(d=1∏?d∑i=1A/d?∑j=1B/d?[gcd(i,j)=1])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}(d=1∏?d∑t=1?μ(t)?tdA???tdB??)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}?????T=1∏?????d∣T∏?dμ(dT?)?????tdA???tdB???????