正题

题目链接:https://www.luogu.com.cn/problem/P5518

---

题目大意

\(T\)次给出\(A,B,C\)求以下三个式子

\[\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^{C}\frac{lcm(i,j)}{gcd(i,k)} \]

\[\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^{C}\left(\frac{lcm(i,j)}{gcd(i,k)}\right)^{i\times j\times k} \]

\[\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)} \]

\(1\leq T\leq 70,1\leq A,B,C\leq 10^5\)

---

解题思路

开始写了个\(O(Tn\log n)\)结果发现不能过，然后就多浪费了三个多小时

只需要用到两个反演的式子

\[F(i)=\sum_{i|d}f(d)\Rightarrow f(i)=\sum_{i|d}\mu(\frac{d}{i})F(d) \]

\[gcd(S)=\sum_{\forall x\in S,d|x}\varphi(d) \]

然后因为推导过程出来冗长以外没有太多难的部分，所以推荐自己手推到不会的再翻题解。

然后就开始吧，因为\(lcm(i,j)=\frac{ij}{gcd(i,j)}\)所以问题可以化为两个部分，求

\[\left(\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^Cij\right)^{f(type)},\left(\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\frac{1}{gcd(i,j)}\right)^{f(type)} \]

首先是第一个式子\(f(type)=1\)。
第一部分就是

\[\prod_{i=1}^Ai^{B\times C}\times \prod_{j=1}^Bj^{A\times C} \]

这个十分简单，我们预处理阶乘就可以做到\(O(\log P)\)
然后第二部分考虑枚举约数

\[\prod_{d=1}\frac{1}{d}^{C\times \sum_{i=1}^A\sum_{j=1}^B[gcd(i,j)=d]} \]

然后莫反

\[\prod_{d=1}\frac{1}{d}^{C\sum_{k=1}\mu(k)\lfloor\frac{A}{kd}\rfloor\lfloor\frac{B}{kd}\rfloor} \]

显然的我们可以\(d,k\)都可以整除分块，预处理一下逆元的前缀乘积就可以快速计算区间逆元乘积了。

第一个式子时间复杂度\(O(n^\frac{3}{4})\)

然后第二个式子类似的，记\(S(n)=\frac{n\times (n+1)}{2}\)那么有

\[\prod_{i=1}^Ai^{iS(B)S(C)}\times \prod_{j=1}^Bj^{jS(A)(C)} \]

维护一个\(i^i\)的前缀积即可。
第二部分

\[\prod_{d=1}\frac{1}{d}^{S(C)\times \sum_{i=1}^A\sum_{j=1}^Bij[gcd(i,j)=d]}\Rightarrow \prod_{d=1}\frac{1}{d}^{S(C)\sum_{k=1}\mu(k)S(\lfloor\frac{A}{kd}\rfloor)S(\lfloor\frac{B}{kd}\rfloor)} \]

需要提前处理\(\mu(i)\times i^2\)的前缀和，\(i^2,\frac{1}{i^2}\)的前缀积就好了

第二个式子时间复杂度\(O(n^\frac{3}{4})\)

主要的难点在第三个式子
首先第一部分先只考虑\(i\)

\[\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^Ci^{gcd(i,j)} \]

考虑欧拉反演，枚举约数

\[\prod_{d=1}\left(\prod_{i}^{\lfloor\frac{A}{d}\rfloor}i\times d\right)^{\varphi(d)\lfloor\frac{B}{d}\rfloor\lfloor\frac{C}{d}\rfloor} \]

设\(f_i=\prod_{j=1}^ii\)那么有

\[\prod_{d=1}\left(f_{\lfloor\frac{A}{d}\rfloor}d^{\lfloor\frac{A}{d}\rfloor}\right)^{\varphi(d)\lfloor\frac{B}{d}\rfloor\lfloor\frac{C}{d}\rfloor} \]

拆开来\(f\)和\(d\)的部分

\[\prod_{d=1}(f_{\lfloor\frac{A}{d}\rfloor})^{\varphi(d)\lfloor\frac{B}{d}\rfloor\lfloor\frac{C}{d}\rfloor}\times d^{\varphi(d)\lfloor\frac{A}{d}\rfloor\lfloor\frac{B}{d}\rfloor\lfloor\frac{C}{d}\rfloor} \]

预处理出\(f\)数组，和\(g\)数组\(g_i=\prod_{j=1}^i j^{\varphi(j)}\)，\(\varphi\)的前缀和就可以整除分块搞了

然后是第二部分

\[\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\frac{1}{gcd(i,j)}^{gcd(i,j,k)} \]

你可以试一下枚举\(gcd(i,j)\)，反正我推了好久都没有对出来/kk
所以考虑枚举\(gcd(i,j,k)\)的约数然后欧拉反演里面再莫反

\[\prod_{d=1}\left(\prod_{k=1}\frac{1}{dk}^{\sum_{z=1}\mu(z)\lfloor\frac{A}{dkz}\rfloor\lfloor\frac{B}{dkz}\rfloor}\right)^{\varphi(d)\lfloor\frac{C}{d}\rfloor} \]

然后把\(\frac{1}{d}\)和\(\frac{1}{k}\)分开处理

\[\prod_{d=1}\left(\prod_{k=1}\frac{1}{k}^{\sum_{z=1}\mu(z)\lfloor\frac{A}{dkz}\rfloor\lfloor\frac{B}{dkz}\rfloor}\right)^{\varphi(d)\lfloor\frac{C}{d}\rfloor} \]

\[\times \prod_{d=1}\left(\frac{1}{d}\right)^{\varphi(d)\lfloor\frac{C}{d}\rfloor\sum_{k=1}\sum_{z=1}\mu(z)\lfloor\frac{A}{dkz}\rfloor\lfloor\frac{B}{dkz}\rfloor} \]

（至于为什么要这么分开，会注意到第一个式子如果我们进行两次整除分块，那么对于每个\(\frac{1}{dk}\)就会有两个影响它的指数\(\varphi(d)\)和\(\sum_{z=1}\mu(z)\lfloor\frac{A}{dkz}\rfloor\lfloor\frac{B}{dkz}\rfloor\)所以很难处理，此时我们分开来就可以直接用区间的值来做了）

注意到这样要做三次整除分块，十分地慢，但是考虑后面那个式子\(\sum_{z=1}\mu(z)\lfloor\frac{A}{dkz}\rfloor\lfloor\frac{B}{dkz}\rfloor\)对于一个固定的\(dk\)是一个确定的值的，并且因为是整除分块，所以不同的值不多我们可以考虑预处理这个东西，整除分块一个\(dk\)然后里面再整除分块计算就好了。

还有拆开后处理\(\frac{1}{d}\)的式子需要预处理\(\frac{1}{d}^{\varphi(d)}\)的前缀积。

然后就做完了，第三部分时间复杂度\(O(n+n^{\frac{3}{4}}\log n)\)

实际上其实最后的式子两个部分可以约掉一些东西省一些常数，但是这样做也能过但是得开int。

或者你可以用别的方法卡卡常反正我开int了。

---

code

因为中途long long改int所以代码巨丑

#include
#include
#include
//#define int long long
using namespace std;
const int N=1e5+10;
int T,P,Phi,A,B,C,ans,cnt;bool v[N];
int pri[N/10],mu[N],su[N],phi[N],f[N],g[N],h[N];
int inv[N],inc[N],inw[N],fac[N],gac[N],hac[N];
int power(int x,int b){
	int ans=1;b=(b%Phi+Phi)%Phi;
	while(b){
		if(b&1)ans=ans*1ll*x%P;
		x=x*1ll*x%P;b>>=1;
	}
	return ans; 
}
int Sum(int n)
{return n*1ll*(n+1)/2%Phi;}
int Tum(int n)
{return n*1ll*(n+1)*1ll*(2ll*1ll*n+1)/6ll%Phi;} 
void Prime(){
	mu[1]=phi[1]=1;
	for(int i=2;i