[MtOI2019]幽灵乐团解题报告

解题报告

[MtOI2019]幽灵乐团解题报告：

题意：共$T$组数据，给定$A,B,C,p$求对于每个$type$的$(\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C(\frac{lcm(i,j)}{\gcd(i,k)})^{f(type)})\bmod p$，其中：$f(type)=\cases{1,\ &type=0\\i\cdot j\cdot k\ &type=1\\\gcd(i,j,k)\ &type=2}$
数据范围：$A,B,C\leqslant 10^5,10^7\leqslant p\leqslant 1.05\cdot 10^9,p\in\mathbb{P},T\leqslant 70$
这道题的公式真的是精神污染。。。
首先我们可以将原式化为$(\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C(\frac{i\cdot j}{\gcd(i,k)^2})^{f(type)})\bmod p$，因此我们可以分为两部分来做这道题，即求$\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=0$时：
  第一个式子：
  

  $$\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C i^{f(0)}=\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C i=\prod_{i=1}^A i^{B\cdot C}=(\prod_{i=1}^A i)^{B\cdot C}$$
  然后用一些基本的套路（枚举$\gcd$，将求积转换为指数的求和，莫比乌斯函数替换$\gcd$，等差数列求和等）化简第二个式子：
  $$\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\gcd(i,j)^{f(0)}=\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\gcd(i,j)=\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)^C\\=(\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j))^C=(\prod_{d=1}^A\prod_{i=1}^A\prod_{j=1}^B d^{[\gcd(i,j)==d]})^C\\=(\prod_{d=1}^A d^{\sum_{i=1}^A\sum_{j=1}^B[\gcd(i,j)==d]})^C=(\prod_{d=1}^A d^{\sum_{i=1}^{\lfloor\frac{A}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{B}{d}\rfloor}[\gcd(i,j)==1]})^C\\=(\prod_{d=1}^A d^{\sum_{i=1}^{\lfloor\frac{A}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{B}{d}\rfloor}\sum_{k\mid\gcd(i,j)}\mu(k)})^C=(\prod_{d=1}^A d^{\sum_{k=1}^{\lfloor\frac{A}{d}\rfloor}\mu(k)\cdot (\sum_{i=1}^{\lfloor\frac{A}{k\cdot d}\rfloor}\sum_{j=1}^{\lfloor\frac{B}{k\cdot d}\rfloor}1)})^C\\=(\prod_{d=1}^A d^{\sum_{k=1}^{\lfloor\frac{A}{d}\rfloor}\mu(k)\cdot\lfloor\frac{A}{k\cdot d}\rfloor\cdot \lfloor\frac{B}{k\cdot d}\rfloor})^C$$
  设$t=k\cdot d$，则有： $$\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C i^{f(0)}=(\prod_{t=1}^A\prod_{d\mid t}d^{\mu(\frac{t}{d})\cdot\lfloor\frac{A}{t}\rfloor\cdot\lfloor\frac{B}{t}\rfloor})^C=(\prod_{t=1}^A(\prod_{d\mid t}d^{\mu(\frac{t}{d})})^{\lfloor\frac{A}{t}\rfloor\cdot\lfloor\frac{B}{t}\rfloor})^C$$
  设$f(x)=\prod_{d\mid x}x^{\mu(\frac{x}{d})}$，则其可以在$O(n\log n)$的时间用整除分块预处理
  此时原式为$(\prod_{t=1}^A f(x)^{\lfloor\frac{A}{t}\rfloor\cdot\lfloor\frac{B}{t}\rfloor})^C$
  可以整除分块解决这一式子
  得分：$20pts$

• $type=1$时：
  第一个式子：
  

  $$\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C i^{f(1)}=\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C i^{i\cdot j\cdot k}=\prod_{i=1}^A i^{i\cdot j\cdot\sum_{k=1}^C k}=\prod_{i=1}^A i^{i\cdot(\sum_{j=1}^B j)\cdot(\sum_{k=1}^C k)}\\=\prod_{i=1}^A i^{i\cdot\frac{B\cdot(B+1)}{2}\cdot\frac{C\cdot(C+1)}{2}}=(\prod_{i=1}^A i^i)^{\frac{B\cdot(B+1)}{2}\cdot\frac{C\cdot(C+1)}{2}}$$
  第二个式子：
  $$\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\gcd(i,j)^{f(1)}=\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\gcd(i,j)^{i\cdot j\cdot k}\\=\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)^{i\cdot j\cdot(\sum_{k=1}^C k)}=\prod_{i=1}^A\prod_{j=1}^B\gcd(i,j)^{i\cdot j\cdot\frac{C\cdot(C+1)}{2}}\\=\prod_{d=1}^n\prod_{i=1}^A\prod_{j=1}^B[\gcd(i,j)==d]d^{i\cdot j\cdot\frac{C\cdot(C+1)}{2}}\\=\prod_{d=1}^A\prod_{i=1}^{\lfloor\frac{A}{d}\rfloor}\prod_{j=1}^{\lfloor\frac{B}{d}\rfloor}[\gcd(i,j)==1]d^{i\cdot j\cdot\frac{C\cdot(C+1)}{2}}\\=(\prod_{d=1}^A\prod_{i=1}^{\lfloor\frac{A}{d}\rfloor}\prod_{j=1}^{\lfloor\frac{B}{d}\rfloor}(\sum_{k\mid\gcd(i,j)}\mu(k))\cdot d^{i\cdot j\cdot d^2})^\frac{C\cdot(C+1)}{2}\\=(\prod_{d=1}^A d^{d^2\cdot \sum_{i=1}^{\lfloor\frac{A}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{B}{d}\rfloor}(i\cdot j\cdot \sum_{k\mid\gcd(i,j)}\mu(k))})^{\frac{C\cdot(C+1)}{2}}\\=(\prod_{d=1}^A d^{d^2\cdot \sum_{k=1}^{\lfloor\frac{A}{d}\rfloor}\mu(k)\sum_{i=1}^{\lfloor\frac{A}{k\cdot d}\rfloor}i\cdot k\sum_{j=1}^{\lfloor\frac{B}{k\cdot d}\rfloor}j\cdot k})^{\frac{C\cdot(C+1)}{2}}\\=(\prod_{d=1}^A d^{\sum_{k=1}^{\lfloor\frac{A}{d}\rfloor}d^2\cdot \mu(k)\cdot k^2\cdot\frac{\lfloor\frac{A}{k\cdot d}\rfloor\cdot (\lfloor\frac{A}{k\cdot d}\rfloor+1)}{2}\cdot\frac{\lfloor\frac{B}{k\cdot d}\rfloor\cdot (\lfloor\frac{B}{k\cdot d}\rfloor+1)}{2}})^{\frac{C\cdot(C+1)}{2}}\\=(\prod_{t=1}^A\prod_{d\mid t} d^{(d^2\cdot (\frac{t}{d})^2)\cdot\mu(\frac{t}{d})\cdot\frac{\lfloor\frac{A}{t}\rfloor\cdot (\lfloor\frac{A}{t}\rfloor+1)}{2}\cdot\frac{\lfloor\frac{B}{t}\rfloor\cdot (\lfloor\frac{B}{t}\rfloor+1)}{2}})^{\frac{C\cdot(C+1)}{2}}\\=(\prod_{t=1}^A(\prod_{d\mid t} d^{\mu(\frac{t}{d})\cdot t^2})^{\frac{\lfloor\frac{A}{t}\rfloor\cdot (\lfloor\frac{A}{t}\rfloor+1)}{2}\cdot\frac{\lfloor\frac{B}{t}\rfloor\cdot (\lfloor\frac{B}{t}\rfloor+1)}{2}})^{\frac{C\cdot(C+1)}{2}}$$
  设$f(x)=(\prod_{d\mid x}x^{\cdot\mu(\frac{x}{d})})^{x^2}$，则$f(x)$可以预处理
  原式可化为： $$\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\gcd(i,j)^{f(1)}=(\prod_{t=1}^A f(t)^{\frac{\lfloor\frac{A}{t}\rfloor\cdot (\lfloor\frac{A}{t}\rfloor+1)}{2}\cdot\frac{\lfloor\frac{B}{t}\rfloor\cdot (\lfloor\frac{B}{t}\rfloor+1)}{2}})^{\frac{C\cdot(C+1)}{2}}$$
  直接整除分块即可
  得分$60pts$

• $type=2$时
  第一个式子：
  

  $$\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C i^{f(2)}=\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C i^{\gcd(i,j,k)}\\=\prod_{i=1}^A i^{\sum_{j=1}^B\sum_{k=1}^C\gcd(i,j,k)}\\=\prod_{i=1}^A i^{\sum_{d=1}^B\sum_{j=1}^B\sum_{k=1}^C[\gcd(i,j,k)==d]\cdot d}\\=\prod_{i=1}^A i^{\sum_{d=1}^B\sum_{j=1}^{\lfloor\frac{B}{d}\rfloor}\sum_{k=1}^{\lfloor\frac{C}{d}\rfloor}[d\mid i][\gcd(\frac{i}{d},j,k)==1]\cdot d}\\=\prod_{i=1}^A i^{\sum_{d\mid i}\sum_{j=1}^{\lfloor\frac{B}{d}\rfloor}\sum_{k=1}^{\lfloor\frac{C}{d}\rfloor}d\cdot (\sum_{r\mid\gcd(\frac{i}{d},j,k)}\mu(r))}\\=\prod_{i=1}^A i^{\sum_{d\mid i}\sum_{r\mid\frac{i}{d}}\sum_{j=1}^{\lfloor\frac{B}{r\cdot d}\rfloor}\sum_{k=1}^{\lfloor\frac{C}{r\cdot d}\rfloor}d\cdot \mu(r))}\\=\prod_{i=1}^A i^{\sum_{d\mid i}d\sum_{r\mid\frac{i}{d}}\mu(r)\sum_{j=1}^{\lfloor\frac{B}{r\cdot d}\rfloor}\sum_{k=1}^{\lfloor\frac{C}{r\cdot d}\rfloor}1}\\=\prod_{i=1}^A i^{\sum_{d\mid i}d\sum_{r\mid\frac{i}{d}}\mu(r)\cdot\lfloor\frac{B}{r\cdot d}\rfloor\cdot\lfloor\frac{C}{r\cdot d}\rfloor}$$
  设$t=r\cdot d$，则有： $$\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C i^{f(2)}=\prod_{i=1}^A i^{\sum_{t\mid n}\lfloor\frac{B}{t}\rfloor\cdot\lfloor\frac{C}{t}\rfloor\sum_{d\mid t}(d\cdot\mu(\frac{t}{d}))}$$
  由$\mu\cdot I=\epsilon$与$\varphi\cdot I=id$，可以简单推一下： $$\varphi\cdot I=id\\\varphi\cdot I\cdot\mu=id\cdot\mu\\\varphi\cdot\epsilon=id\cdot\mu\\\varphi=id\cdot\mu\\\varphi(x)=\sum_{d\mid x} d\cdot\mu(\frac{x}{d})$$
  因此带入原式得： $$\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C i^{f(2)}=\prod_{i=1}^A i^{\sum_{t\mid n}\lfloor\frac{B}{t}\rfloor\cdot\lfloor\frac{C}{t}\rfloor\varphi(t)}\\=\prod_{i=1}^A\prod_{t\mid i} i^{\varphi(t)\cdot \lfloor\frac{B}{t}\rfloor\cdot\lfloor\frac{C}{t}\rfloor}=\prod_{t=1}^A\prod_{i=1}^{\lfloor\frac{A}{t}\rfloor} (i\cdot t)^{\varphi(t)\cdot \lfloor\frac{B}{t}\rfloor\cdot\lfloor\frac{C}{t}\rfloor}$$
  注意一下，这里$i$扩大$t$倍的原因是$i$的范围缩小了$t$
  继续推： $$\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C i^{f(2)}=\prod_{t=1}^A(t^{\lfloor\frac{A}{t}\rfloor}\cdot\prod_{i=1}^{\lfloor\frac{A}{t}\rfloor}i)^{\varphi(t)\cdot \lfloor\frac{B}{t}\rfloor\cdot\lfloor\frac{C}{t}\rfloor}\\=\prod_{t=1}^A ((t^{\varphi(t)})^{\lfloor\frac{A}{t}\rfloor\cdot\lfloor\frac{B}{t}\rfloor\cdot\lfloor\frac{C}{t}\rfloor}\cdot(\prod_{i=1}^{\lfloor\frac{A}{t}\rfloor}i)^{\varphi(t)\cdot\lfloor\frac{B}{t}\rfloor\cdot\lfloor\frac{C}{t}\rfloor})$$
  设$fac(i)$为$i$的阶乘，则原式可化为： $$\prod_{t=1}^A ((t^{\varphi(t)})^{\lfloor\frac{A}{t}\rfloor\cdot\lfloor\frac{B}{t}\rfloor\cdot\lfloor\frac{C}{t}\rfloor}\cdot fac(\lfloor\frac{A}{t}\rfloor)^{\varphi(t)\cdot\lfloor\frac{B}{t}\rfloor\cdot\lfloor\frac{C}{t}\rfloor})$$
  然后预处理+整除分块就可以解决了
  第二个式子：
  $$\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\gcd(i,j)^{f(2)}=\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\gcd(i,j)^{\gcd(i,j,k)}$$
  枚举$\gcd(i,j)$： $$\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\gcd(i,j)^{f(2)}\\=\prod_{d=1}^A\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C[\gcd(i,j)==d]\cdot d^{\gcd(i,j,k)}\\=\prod_{d=1}^A d^{\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C[\gcd(i,j)==d]\cdot\gcd(i,j,k)}\\=\prod_{d=1}^A d^{\sum_{i=1}^{\lfloor\frac{A}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{B}{d}\rfloor}\sum_{k=1}^C[\gcd(i,j)==1]\cdot\gcd(d,k)}\\=\prod_{d=1}^A d^{\sum_{i=1}^{\lfloor\frac{A}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{B}{d}\rfloor}\sum_{k=1}^C(\sum_{r\mid\gcd(i,j)}\mu(r))\cdot\gcd(d,k)}\\=\prod_{d=1}^A d^{\sum_{r=1}^{\lfloor\frac{A}{d}\rfloor}\mu(r)\sum_{i=1}^{\lfloor\frac{A}{r\cdot d}\rfloor}\sum_{j=1}^{\lfloor\frac{B}{r\cdot d}\rfloor}\sum_{k=1}^C\gcd(d,k)}\\=\prod_{d=1}^A d^{\sum_{r=1}^{\lfloor\frac{A}{d}\rfloor}\mu(r)\cdot\lfloor\frac{A}{r\cdot d}\rfloor\cdot\lfloor\frac{B}{r\cdot d}\rfloor(\sum_{k=1}^C\gcd(d,k))}$$
  设$t=r\cdot d$，则有： $$\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\gcd(i,j)^{f(2)}=\prod_{t=1}^A\prod_{d\mid t}d^{\mu(\frac{t}{d})\cdot\lfloor\frac{A}{t}\rfloor\cdot\lfloor\frac{B}{t}\rfloor(\sum_{k=1}^C\gcd(d,k))}$$
  我们将$\sum_{k=1}^C\gcd(d,k)$单独拿出推一下： $$\sum_{k=1}^C\gcd(d,k)=\sum_{w\mid d}\sum_{k=1}^C[\gcd(d,k)==w]\cdot w\\=\sum_{w\mid d} w\sum_{k=1}^{\lfloor\frac{C}{w}\rfloor}[\gcd(\frac{d}{w},k)==1]=\sum_{w\mid d}w\sum_{k=1}^{\lfloor\frac{C}{w}\rfloor}\sum_{g\mid\gcd(\frac{d}{w},k)}\mu(g)\\=\sum_{w\mid d}w\sum_{g\mid\frac{d}{w}}\mu(g)\cdot\lfloor\frac{C}{w\cdot g}\rfloor$$
  设$h=w\cdot g$，则有： $$\sum_{k=1}^C\gcd(d,k)=\sum_{h\mid d}\sum_{w\mid h}w\cdot\mu(\frac{h}{w})\cdot\lfloor\frac{C}{h}\rfloor$$
  由上面推出的$\varphi(x)=\sum_{d\mid x} d\cdot\mu(\frac{x}{d})$带入上式得 $$\sum_{k=1}^C\gcd(d,k)=\sum_{h\mid d}\varphi(h)\cdot\lfloor\frac{C}{h}\rfloor$$
  将其代入原式得： $$\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C i^{f(2)}=\prod_{t=1}^A\prod_{d\mid t}d^{\mu(\frac{t}{d})(\sum_{h\mid d}\varphi(h)\cdot\lfloor\frac{C}{h}\rfloor)\cdot \lfloor\frac{A}{t}\rfloor\cdot\lfloor\frac{B}{t}\rfloor}\\=\prod_{t=1}^A\prod_{d\mid t}\prod_{h\mid d}d^{\mu(\frac{t}{d})\varphi(h)\cdot\lfloor\frac{C}{h}\rfloor\cdot \lfloor\frac{A}{t}\rfloor\cdot\lfloor\frac{B}{t}\rfloor}$$
  这里需要比较毒瘤将$d$拆成$\frac{d}{h}\cdot h$，我们先计算$\frac{d}{h}$的情况：
  改变求和顺序并先后将$t$与$d$扩大$h$倍得原式可以化为：
  $$\prod_{h=1}^A\prod_{t=1}^{\lfloor\frac{A}{h}\rfloor}\prod_{h\mid d,d\mid h\cdot t}\frac{d}{h}^{\mu(\frac{h\cdot t}{d})\cdot\varphi(h)\cdot\lfloor\frac{C}{h}\rfloor\cdot\lfloor\frac{A}{h\cdot t}\rfloor\cdot\lfloor\frac{B}{h\cdot t}\rfloor}\\=\prod_{h=1}^A\prod_{t=1}^{\lfloor\frac{A}{h}\rfloor}\prod_{d\mid t}d^{\mu(\frac{h\cdot t}{d\cdot h})\cdot\varphi(h)\cdot\lfloor\frac{C}{h}\rfloor\cdot\lfloor\frac{A}{h\cdot t}\rfloor\cdot\lfloor\frac{B}{h\cdot t}\rfloor}\\=\prod_{h=1}^A(\prod_{t=1}^{\lfloor\frac{A}{h}\rfloor}(\prod_{d\mid t}d^{\mu(\frac{t}{d})})^{\lfloor\frac{A}{h\cdot t}\rfloor\cdot\lfloor\frac{B}{h\cdot t}\rfloor})^{\varphi(h)\cdot\lfloor\frac{C}{h}\rfloor}$$
  设$f(x)=\sum_{d\mid x}d^{\mu(\frac{x}{d})}$，则$f(x)$可在$O(n\log n)$的时间内预处理
  则原式可化为 $$\prod_{h=1}^A(\prod_{t=1}^{\lfloor\frac{A}{h}\rfloor}f(t)^{\lfloor\frac{A}{h\cdot t}\rfloor\cdot\lfloor\frac{B}{h\cdot t}\rfloor})^{\varphi(h)\cdot\lfloor\frac{C}{h}\rfloor}$$
  然后我们计算$h$的情况：
  同样我们可以改变求和顺序，先后将$t$和$d$扩大$h$倍
  $$\prod_{t=1}^A\prod_{d\mid t}\prod_{h\mid d}h^{\mu(\frac{t}{d})\varphi(h)\cdot\lfloor\frac{C}{h}\rfloor\cdot \lfloor\frac{A}{t}\rfloor\cdot\lfloor\frac{B}{t}\rfloor}=\prod_{h=1}^A\prod_{t=1}^{\lfloor\frac{A}{h}\rfloor}\prod_{h\mid d,d\mid h\cdot t} h^{\mu(\frac{h\cdot t}{d})\varphi(h)\cdot\lfloor\frac{C}{h}\rfloor\cdot \lfloor\frac{A}{t}\rfloor\cdot\lfloor\frac{B}{t}\rfloor}\\=\prod_{h=1}^A\prod_{t=1}^{\lfloor\frac{A}{h}\rfloor}\prod_{d\mid t} h^{\mu(\frac{h\cdot t}{d\cdot h}\cdot\varphi(h))\cdot \lfloor\frac{C}{h}\rfloor\cdot\lfloor\frac{A}{h\cdot t}\rfloor\cdot\lfloor\frac{B}{h\cdot t}\rfloor}\\=\prod_{h=1}^A\prod_{t=1}^{\lfloor\frac{A}{h}\rfloor}\prod_{d\mid t} h^{\mu(\frac{t}{d}\cdot\varphi(h))\cdot \lfloor\frac{C}{h}\rfloor\cdot\lfloor\frac{A}{h\cdot t}\rfloor\cdot\lfloor\frac{B}{h\cdot t}\rfloor}$$
  将求积改成指数求和得：
  $$\prod_{t=1}^A\prod_{d\mid t}\prod_{h\mid d}h^{\mu(\frac{t}{d})\varphi(h)\cdot\lfloor\frac{C}{h}\rfloor\cdot \lfloor\frac{A}{t}\rfloor\cdot\lfloor\frac{B}{t}\rfloor}=\prod_{h=1}^A h^{\sum_{t=1}^{\lfloor\frac{A}{h}\rfloor}\sum_{d\mid t}\mu(\frac{t}{d})\cdot\varphi(h)\cdot \lfloor\frac{C}{h}\rfloor\cdot\lfloor\frac{A}{h\cdot t}\rfloor\cdot\lfloor\frac{B}{h\cdot t}\rfloor}\\=\prod_{h=1}^A h^{\varphi(h)\cdot\lfloor\frac{C}{h}\rfloor\cdot \sum_{t=1}^{\lfloor\frac{A}{h}\rfloor} \lfloor\frac{A}{h\cdot t}\rfloor\cdot\lfloor\frac{B}{h\cdot t}\rfloor\sum_{d\mid t}\mu(\frac{t}{d})}$$
  由莫比乌斯反演$\mu\cdot I=\epsilon$得：
  $$\prod_{t=1}^A\prod_{d\mid t}\prod_{h\mid d}h^{\mu(\frac{t}{d})\varphi(h)\cdot\lfloor\frac{C}{h}\rfloor\cdot \lfloor\frac{A}{t}\rfloor\cdot\lfloor\frac{B}{t}\rfloor}=\prod_{h=1}^A h^{\varphi(h)\cdot\lfloor\frac{C}{h}\rfloor\cdot \sum_{t=1}^{\lfloor\frac{A}{h}\rfloor} \lfloor\frac{A}{h\cdot t}\rfloor\cdot\lfloor\frac{B}{h\cdot t}\rfloor\epsilon(t)}\\=\prod_{h=1}^A h^{\varphi(h)\cdot\lfloor\frac{C}{h}\rfloor\cdot \sum_{t=1}^{\lfloor\frac{A}{h}\rfloor} [t==1]\cdot \lfloor\frac{A}{h\cdot t}\rfloor\cdot\lfloor\frac{B}{h\cdot t}\rfloor}\\=\prod_{h=1}^A h^{\varphi(h)\cdot\lfloor\frac{C}{h}\rfloor\cdot \lfloor\frac{A}{h\cdot 1}\rfloor\cdot\lfloor\frac{B}{h\cdot 1}\rfloor}\\=\prod_{h=1}^A h^{\varphi(h)\cdot\lfloor\lfloor\frac{A}{h}\rfloor\cdot\lfloor\frac{B}{h}\rfloor\cdot\frac{C}{h}\rfloor}$$
  故 $$\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\gcd(i,j)^{f(2)}=\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\gcd(i,j)^{\gcd(i,j,k)}\\=(\prod_{h=1}^A(\prod_{t=1}^{\lfloor\frac{A}{h}\rfloor}f(t)^{\lfloor\frac{A}{h\cdot t}\rfloor\cdot\lfloor\frac{B}{h\cdot t}\rfloor})^{\varphi(h)\cdot\lfloor\frac{C}{h}\rfloor})\cdot (\prod_{h=1}^A h^{\varphi(h)\cdot\lfloor\frac{A}{h}\rfloor\cdot\lfloor\frac{B}{h}\rfloor\cdot\lfloor\frac{C}{h}\rfloor})\\=\prod_{h=1}^A((\prod_{t=1}^{\lfloor\frac{A}{h}\rfloor}f(t)^{\lfloor\frac{A}{h\cdot t}\rfloor\cdot\lfloor\frac{B}{h\cdot t}\rfloor})^{\varphi(h)\cdot\lfloor\frac{C}{h}\rfloor}\cdot h^{\varphi(h)\cdot\lfloor\frac{A}{h}\rfloor\cdot\lfloor\frac{B}{h}\rfloor\cdot\lfloor\frac{C}{h}\rfloor})$$
  （$f(x)=\sum_{d\mid x}d^{\mu(\frac{x}{d})}$）

#include<stdio.h>
const int maxn=100005;
long long i,j,k,m,n,T,p,A,B,C,l,r,cnt;
long long a[maxn],c[maxn],mu[maxn],varphi[maxn],fac1[maxn],fac2[maxn],w1[maxn],f1[maxn],g1[maxn],w2[maxn],f2[maxn],g2[maxn],w3[maxn],f3[maxn],g3[maxn],sum[maxn];
//a[i]={Prime},c[i]=[i\in{Prime}?]
//mu[i]=(i==1?)1:((i=\prod_{j=1}^s p_i,(p_x!=p_y(x!=y)))? 0:(-1)^s)
//fac1[i]=i!,fac2[i]=\prod_{j=1}^i i^i
//w1[i]=\prod_{d|i}i^{\mu(d/i)},f1[i]=\prod_{j=1}^i w1[i],g1[i]=f1[i]^{-1}
//w2[i]=w1[i]*(i^2),f2[i]=\prod_{j=1}^i w2[i],g2[i]=f2[i]^{-1}
//w3[i]=i^{\varphi(i)},f3[i]=\prod_{j=1]^i w3[i],g3[i]=f3[i]^{-1}
//sum[i]=\sum_{j=1}^i varphi[i]
inline long long min(long long a,long long b){
    return a<b? a:b;
}
long long ksm(long long a,long long b,long long p){
    long long res=1;
    while(b>0){
        if(b&1)
            res=(res*a)%p;
        a=(a*a)%p,b>>=1;
    }
    return res;
}
long long inv(long long a,long long b){
    return ksm(a,b-2,b);
}
void init(){
    c[1]=mu[1]=varphi[1]=1;
    for(long long i=2;i<maxn;i++){
        if(c[i]==0)
            a[++cnt]=i,mu[i]=-1,varphi[i]=i-1;
        for(long long j=1;j<=cnt;j++){
            if(i*a[j]>=maxn)
                break;
            c[i*a[j]]=1;
            if(i%a[j]==0){
                mu[i*a[j]]=0;
                varphi[i*a[j]]=varphi[i]*a[j];
                break;
            }
            mu[i*a[j]]=-mu[i];
            varphi[i*a[j]]=varphi[i]*(a[j]-1);
        }
    }
    fac1[0]=1;
    for(long long i=1;i<maxn;i++)
        fac1[i]=fac1[i-1]*i%p; 
    fac2[0]=1;
    for(long long i=1;i<maxn;i++)
        fac2[i]=fac2[i-1]*ksm(i,i%(p-1),p)%p; 
    for(long long i=0;i<maxn;i++)
        w1[i]=w2[i]=1;
    for(long long i=1;i<maxn;i++){
        if(mu[i]==0)
            continue;
        for(long long j=i;j<maxn;j+=i){
            if(mu[i]==1)
                w1[j]=(w1[j]*(j/i))%p;
            if(mu[i]==-1)
                w1[j]=(w1[j]*inv(j/i,p))%p;
        }
    }
    f1[0]=g1[0]=1;
    for(long long i=1;i<maxn;i++)
        f1[i]=f1[i-1]*w1[i]%p,g1[i]=inv(f1[i],p);
    for(long long i=1;i<maxn;i++)
        w2[i]=ksm(w1[i],i*i%(p-1),p);
    f2[0]=g2[0]=1;
    for(long long i=1;i<maxn;i++)
        f2[i]=f2[i-1]*w2[i]%p,g2[i]=inv(f2[i],p);
    for(long long i=1;i<maxn;i++)
        w3[i]=ksm(i,varphi[i],p);
    f3[0]=g3[0]=1;
    for(long long i=1;i<maxn;i++)
        f3[i]=f3[i-1]*w3[i]%p,g3[i]=inv(f3[i],p);
    for(long long i=1;i<maxn;i++)
        sum[i]=sum[i-1]+varphi[i];
}
inline long long getsum(long long x,long long p){
    return x*(x+1)/2%p;
}
long long getnmt(long long A,long long B,long long C,long long t){
    if(t==0){
        long long res=ksm(fac1[A],B*C%(p-1),p);
        return res;
    } 
    if(t==1){
        long long res=ksm(fac2[A],getsum(B,p-1)*getsum(C,p-1)%(p-1),p);
        return res;
    }
    if(t==2){
        long long l=1,r,res=1;
        while(l<=min(min(A,B),C)){
            r=min(min(A/(A/l),B/(B/l)),C/(C/l));
            res=res*ksm(f3[r]*g3[l-1]%p,(A/l)*(B/l)%(p-1)*(C/l)%(p-1),p)%p*ksm(fac1[A/l],(sum[r]-sum[l-1]+(p-1))%(p-1)*(B/l)%(p-1)*(C/l)%(p-1),p)%p;
            l=r+1;
        }
        return res;
    }
}
long long getres(long long A,long long B){
    long long l=1,r,res=1;
    while(l<=min(A,B)){
        r=min(A/(A/l),B/(B/l));
        res=res*ksm(f1[r]*g1[l-1]%p,(A/l)*(B/l)%(p-1),p)%p;
        l=r+1;
    }
    return res;
}
long long getdmt(long long A,long long B,long long C,long long t){
    if(t==0){ 
        long long l=1,r,res=1;
        while(l<=min(A,B)){
            r=min(A/(A/l),B/(B/l));
            res=(res*ksm(f1[r]*g1[l-1]%p,(A/l)*(B/l)%(p-1),p))%p;
            l=r+1;
        }
        return ksm(res,C,p);
    }
    if(t==1){
        long long l=1,r,res=1;
        while(l<=min(A,B)){
            r=min(A/(A/l),B/(B/l));
            res=(res*ksm(f2[r]*g2[l-1]%p,getsum(A/l,p-1)*getsum(B/l,p-1)%(p-1),p))%p;
            l=r+1;
        }
        return ksm(res,getsum(C,p-1),p);
    }
    if(t==2){
        long long l=1,r,res=1;
        while(l<=min(min(A,B),C)){
            r=min(min(A/(A/l),B/(B/l)),C/(C/l));
            res=res*ksm(getres(A/l,B/l),(sum[r]-sum[l-1]+(p-1))%(p-1)*(C/l)%(p-1),p)%p*ksm(f3[r]*g3[l-1]%p,(A/l)*(B/l)%(p-1)*(C/l)%(p-1),p)%p;
            l=r+1;
        }
        return res;
    }
}
long long getans(long long A,long long B,long long C,long long t){
    long long nmt=getnmt(A,B,C,t)*getnmt(B,A,C,t)%p,dmt=getdmt(A,B,C,t)*getdmt(A,C,B,t)%p;
    return nmt*inv(dmt,p)%p;
}
int main(){
    scanf("%lld%lld",&T,&p);
    init();
    while(T--){
        scanf("%lld%lld%lld",&A,&B,&C);
        printf("%lld %lld %lld\n",getans(A,B,C,0),getans(A,B,C,1),getans(A,B,C,2)); 
    }
    return 0;
}