题意
求下面表达式的值，
\[\prod_{i=1}^{A} \prod_{j=1}^{B} \prod_{k=1}^{C} \left( \frac{lcm(i,j)}{gcd(i,k)} \right)^{f(type)} \pmod{p} \]其中，\(type=\{0,1,2\}\)，\(f(type)\)满足：
\[f(0)=1, \]\[f(1)=i \times j \times k, \]\[f(2) = gcd(i,j,k). \]其中， \(A,B,C \leqslant 10^5.\)
Solution
type = 0
拿到这个式子非常兴奋，然后就开始疯狂化简，最终化简成了一个\(O(n\sqrt{n} \log {n})\)的表达式，非常沮丧的是不能满足题目的要求。
我们重新分析这个式子，
\[\prod_{i=1}^{A} \prod_{j=1}^{B} \prod_{k=1}^{C} \left( \frac{lcm(i,j)}{gcd(i,k)} \right) \]\[=\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) \]不难发现，这个式子的\(i,j,k\)是对称的，相当于我们仅需要计算以下两部分式子的值，然后将其组合起来，
\[\prod_{i=1}^{A} \prod_{j=1}^{B} \prod_{k=1}^{C} i \]\[\prod_{i=1}^{A} \prod_{j=1}^{B} \prod_{k=1}^{C} \frac{1}{gcd(i,j)} \]分别来对两个式子进行化简
\[\prod_{i=1}^{A} \prod_{j=1}^{B} \prod_{k=1}^{C} i \]\[= \prod_{i=1}^{A} i ^ {BC} \]\[= \left( \prod_{i=1}^{A} i \right) ^ {BC} \]可以通过预处理前缀积\(O(\log{n})\)实现对于此式的计算。
\[\prod_{i=1}^{A} \prod_{j=1}^{B} \prod_{k=1}^{C} \frac{1}{gcd(i,j)} \pmod{p} \]\[=\left(\prod_{i=1}^{A} \prod_{j=1}^{B} \prod_{k=1}^{C} gcd(i,j) \right)^{-1} \pmod{p} \]接下来只计算其本身的值，然后再计算逆元求出答案。
\[\prod_{i=1}^{A} \prod_{j=1}^{B} \prod_{k=1}^{C} gcd(i,j) \]\[=\left(\prod_{i=1}^{A} \prod_{j=1}^{B} gcd(i,j)\right)^{C} \]\[\Large {=\left(\prod_{d=1}^{min\{A,B,C\}} d ^{\sum_{i=1}^{\lfloor \frac{A}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{B}{d} \rfloor } \sum_{x|i, x|j} \mu(x)}\right)^{C}} \]跟[SDOI2017]数字表格类似的，则有，
\[\Large {\left(\prod_{T=1}^{min\{A,B\}} ( \prod_{d|T} d^{\mu(\frac{T}{x})} ) ^ {\lfloor \frac{A}{T} \rfloor \lfloor \frac{B}{T} \rfloor}\right) ^ C } \]里面的部分在上述题目中已经处理过了，只需要计算最终得到值的\(C\)次幂，便可以计算出此答案。
type = 1
大致的思路显然跟上面类似，重新推一遍两个式子即可。
\[\prod_{i=1}^{A} \prod_{j=1}^{B} \prod_{k=1}^{C} i ^ {ijk} \]\[=\prod_{i=1}^{A} \prod_{j=1}^{B} \prod_{k=1}^{C} (i ^ {i}) ^ {jk} \]\[= (\prod_{i=1}^{A} i ^ {i}) ^ {\sum_{j=1}^{B} \sum_{k=1}^{C} jk} \]记\(S(n) = \sum_{i=1}^{n} i = \frac{n \times (n + 1)}{2}\)，则有，
\[= (\prod_{i=1}^{A} i ^ {i}) ^ {S(B) \ S(C)} \]与\(type=0\)类似的，我们可以通过预处理 \(i^i\)的前缀积，然后可以在\(O(\log{n})\)的时间复杂度内求解这一部分的值。
\[\prod_{i=1}^{A} \prod_{j=1}^{B} \prod_{k=1}^{C} (gcd(i,j))^{ijk} \]\[=\left(\prod_{i=1}^{A} \prod_{j=1}^{B} (gcd(i,j))^{ij} \right) ^ {S(C)} \]\[\Large{=\left(\prod_{d=1}^{min\{A,B\}} d^{d^2 \sum_{i=1}^{\lfloor \frac{A}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{B}{d} \rfloor} i \times j \sum_{x|i, x|j}\mu(x)} \right) ^ {S(C)}} \]\[\Large{=\left(\prod_{d=1}^{min\{A,B\}} d^{d^2 \sum_{x=1}^{min\{\lfloor \frac{A}{d} \rfloor,\lfloor \frac{B}{d} \rfloor\}}x^2\mu(x)S(\lfloor \frac{A}{xd} \rfloor)\ S(\lfloor \frac{B}{xd} \rfloor)} \right) ^ {S(C)}} \]记\(T=xd\)，则有，
\[\large{\left( \prod_{T=1}^{min\{A,B\}} ( \prod_{d|T} d^{d^2 \mu(\frac{T}{d})} )^{S(\lfloor \frac{A}{T} \rfloor) S(\lfloor \frac{B}{T} \rfloor)} \right) ^ {S(C)} } \]类似\(type=0\)，不难发现 $\prod_{d|T} d ^ {d^2 \mu(\frac{T}{d})} $ 可以枚举因子进行计算，在 \(O(n\sqrt{n})\) 的时间复杂度下完成预处理。
然后对\(T\)进行数论分块，可以在 \(O(\log{n} \sqrt{n}\) 下完成整个式子的计算。
type = 2
60pts
貌似可以卡常a掉这题？反正我的常数太大了（
感谢洛谷题解区peterwuyihong的idea。
对于比较复杂的质数问题，我们可以想到将其进行\(ln\)和\(exp\)操作。
\[\prod_{i=1}^A \prod_{j=1}^B \prod_{k=1}^{C} \left( \frac{lcm(i,j)}{gcd(i,k) }\right) ^ {gcd(i,j,k)} \]对他取\(ln\)操作：
\[\sum_{i=1}^A \sum_{j=1}^B \sum_{k=1}^{C} \ln{\left( \frac{lcm(i,j)}{gcd(i,k) }\right)} \times gcd(i,j,k) \]莫比乌斯经典枚举因子，则有，
\[= \sum_{d=1}^{min\{A,B,C\}} \sum_{i=1}^A \sum_{j=1}^B \sum_{k=1}^C \ln{ ( \frac{lcm(i,j)}{gcd(i,k)} ) } \times d \times [gcd(i,j,k)=d] \]\[= \sum_{d=1}^{min\{A,B,C\}} d \sum_{i=1}^{\lfloor \frac{A}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{B}{d} \rfloor} \sum_{k=1}^{\lfloor \frac{C}{d} \rfloor} \ln{ ( \frac{lcm(id,jd)}{gcd(id,kd)} ) } \times [gcd(i,j,k)=1] \]\[= \sum_{d=1}^{min\{A,B,C\}} d\sum_{i=1}^{\lfloor \frac{A}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{B}{d} \rfloor} \sum_{k=1}^{\lfloor \frac{C}{d} \rfloor} \ln{ ( \frac{lcm(id,jd)}{gcd(id,kd)} ) } \sum_{x|gcd(i,j,k)} \mu(x) \]\[= \sum_{d=1}^{min\{A,B,C\}} d\sum_{x=1}^{min\{\lfloor \frac{A}{d} \rfloor,\lfloor \frac{B}{d} \rfloor\lfloor \frac{C}{d} \rfloor\}} \mu(x) \sum_{i=1}^{\lfloor \frac{A}{xd} \rfloor} \sum_{j=1}^{\lfloor \frac{B}{xd} \rfloor} \sum_{k=1}^{\lfloor \frac{C}{xd} \rfloor} \ln{ ( \frac{lcm(ixd,jxd)}{gcd(ixd,kxd)} ) } \]记\(T=xd\)，则有
\[= \sum_{T=1}^{min\{A,B,C\}} \sum_{d|T} (\mu(d) \frac{T}{d} \sum_{i=1}^{\lfloor \frac{A}{T} \rfloor} \sum_{j=1}^{\lfloor \frac{B}{T} \rfloor} \sum_{k=1}^{\lfloor \frac{C}{T} \rfloor} \ln{ ( \frac{lcm(iT,jT)}{gcd(iT,kT)} )} \]\[= \sum_{T=1}^{min\{A,B,C\}} \sum_{d|T} (\mu(d) \frac{T}{d} )\sum_{i=1}^{\lfloor \frac{A}{T} \rfloor} \sum_{j=1}^{\lfloor \frac{B}{T} \rfloor} \sum_{k=1}^{\lfloor \frac{C}{T} \rfloor} \ln{ ( \frac{lcm(i,j)}{gcd(i,k)} )} \]\[= \sum_{T=1}^{min\{A,B,C\}} \varphi(T)\sum_{i=1}^{\lfloor \frac{A}{T} \rfloor} \sum_{j=1}^{\lfloor \frac{B}{T} \rfloor} \sum_{k=1}^{\lfloor \frac{C}{T} \rfloor} \ln{ ( \frac{lcm(i,j)}{gcd(i,k)} )} \]然后将其\(exp\)一下，得到结果，
\[= \prod_{T=1}^{min\{A,B,C\}} (\prod_{i=1}^{\lfloor \frac{A}{T} \rfloor} \prod_{j=1}^{\lfloor \frac{B}{T} \rfloor} \prod_{k=1}^{\lfloor \frac{C}{T} \rfloor} \frac{lcm(i,j)}{gcd(i,k)} )^{\varphi(T)} \]\[= \prod_{T=1}^{min\{A,B,C\}} ANS_{type=0}(\lfloor \frac{A}{T} \rfloor,\lfloor \frac{B}{T} \rfloor,\lfloor \frac{C}{T} \rfloor)^{\varphi(T)} \]然后可以调用\(type=1\)的结果，就可以完成计算，但是由于\(type=2\)时多存在一个\(O(\sqrt{n})\)，故在时间上比较紧张。
100pts
先让我研究明白awa
Code
还没写完，别急awa
后记
这个题的数学公式也太复杂了...
不得不把公式字体放大，然后又显得太蠢了...
莫比乌斯反演《基础》练习题