#莫比乌斯反演，欧拉函数#洛谷 5518 [MtOI2019]幽灵乐团
题目传送门
分析
前置知识：\(\sum_{d|n}\mu(d)=[n==1]\),\(\sum_{d|n}\mu(d)\frac{n}{d}=\varphi(n)\)
把最小公倍数拆开可以得到
\[=\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\left(\frac{ij}{\gcd(i,j)\gcd(i,k)}\right)^{f(type)} \]一个一个类型解决，并且拆开分子分母，先看 \(type=0\) 的情况，
分子 \(=\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C(ij)=[(A!)^B(B!)^A]^C\)
分母以 \(\gcd(i,j)\) 为例也即是 \(=\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\gcd(i,j)\)
枚举 \(d=\gcd(i,j)\) 也即是
\[\large =\left(\prod_{d=1}^{\min\{A,B\}}d^{\sum_{i=1}^{\left\lfloor\frac{A}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{B}{d}\right\rfloor}[\gcd(i,j)==1]}\right)^C \]\[\large =\left(\prod_{d=1}^{\min\{A,B\}}\prod_{t=1}^{\min\left\{\left\lfloor\frac{A}{d}\right\rfloor,\left\lfloor\frac{B}{d}\right\rfloor\right\}}d^{\mu(t)\left\lfloor\frac{A}{dt}\right\rfloor\left\lfloor\frac{B}{dt}\right\rfloor}\right)^C \]枚举 \(i=dt\) 即
\[\large =\left(\prod_{i=1}^{\min\{A,B\}}\left[\prod_{d|i}d^{\mu\left(\frac{i}{d}\right)}\right]^{\left\lfloor\frac{A}{i}\right\rfloor\left\lfloor\frac{B}{i}\right\rfloor}\right)^C \]设 \(f(n)=\prod_{d|n}d^{\mu\left(\frac{n}{d}\right)}\)，然后整个就可以整除分块。
设 \(S1(A,B)=\prod_{i=1}^{\min\{A,B\}}f(i)^{\left\lfloor\frac{A}{i}\right\rfloor\left\lfloor\frac{B}{i}\right\rfloor}\)
那么合起来当 \(type=0\) 时答案为 \(\large \frac{\left[(A!)^B(B!)^A\right]^C}{S1(A,B)^CS1(A,C)^B}\)
再看 \(type=1\) 的情况，设 \(c2(n)=\binom{n+1}{2}\) 分子为
\[\large =\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C(ij)^{ijk}=\left[\prod_{i=1}^A\left(i^i\right)^{c2(B)}\prod_{j=1}^B\left(j^j\right)^{c2(A)}\right]^{c2(C)} \]设 \(g(n)=\prod_{i=1}^n\left(i^i\right)\)，那也就是 \(=\left[g(A)^{c2(B)}g(B)^{c2(A)}\right]^{c2(C)}\)
分母同样以 \(\gcd(i,j)\) 为例， 即为 \(\prod_{i=1}^A\prod_{j=1}^B\prod_{k=1}^C\gcd(i,j)^{ijk}\)
枚举 \(d=\gcd(i,j)\)，也即是
\[\large =(\prod_{d=1}^{\min\{A,B\}}d^{d^2\sum_{i=1}^{\left\lfloor\frac{A}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{B}{d}\right\rfloor}ij[\gcd(i,j)==1]})^{c2(C)} \]\[\large =\left(\prod_{d=1}^{\min\{A,B\}}\prod_{t=1}^{\min\left\{\left\lfloor\frac{A}{d}\right\rfloor,\left\lfloor\frac{B}{d}\right\rfloor\right\}}d^{(dt)^2\mu(t)\left\lfloor\frac{A}{dt}\right\rfloor\left\lfloor\frac{B}{dt}\right\rfloor}\right)^{c2(C)} \]枚举 \(i=dt\) 即
\[\large =\left(\prod_{i=1}^{\min\{A,B\}}\left[\prod_{d|i}d^{\mu\left(\frac{i}{d}\right)}\right]^{i^2\left\lfloor\frac{A}{i}\right\rfloor\left\lfloor\frac{B}{i}\right\rfloor}\right)^{c2(C)} \]设 \(S2(A,B)=\prod_{i=1}^{\min\{A,B\}}f(i)^{i^2\left\lfloor\frac{A}{i}\right\rfloor\left\lfloor\frac{B}{i}\right\rfloor}\)
那么合起来当 \(type=1\) 时答案为 \(\large \frac{\left[g(A)^{c2(B)}g(B)^{c2(A)}\right]^{c2(C)}}{S2(A,B)^CS2(A,C)^B}\)
再看 \(type=2\) 的情况，
分子 \(=\prod_{i=1}^{A}\prod_{j=1}^B\prod_{k=1}^C(ij)^{\gcd(i,j,k)}\)
枚举 \(d=\gcd(i,j,k)\)，也即是
\[=\prod_{d=1}^{\min\{A,B,C\}}\prod_{i=1}^{\left\lfloor\frac{A}{d}\right\rfloor}\prod_{j=1}^{\left\lfloor\frac{B}{d}\right\rfloor}\prod_{k=1}^{\left\lfloor\frac{C}{d}\right\rfloor}(ijd^2)^{d[gcd(i,j,k)==1]} \]\[=\prod_{d=1}^{\min\{A,B,C\}}\prod_{t=1}^{\min\left\{\left\lfloor\frac{A}{d}\right\rfloor,\left\lfloor\frac{B}{d}\right\rfloor,\left\lfloor\frac{C}{d}\right\rfloor\right\}}\prod_{i=1}^{\left\lfloor\frac{A}{dt}\right\rfloor}\prod_{j=1}^{\left\lfloor\frac{B}{dt}\right\rfloor}\prod_{k=1}^{\left\lfloor\frac{C}{dt}\right\rfloor}(ij(dt)^2)^{d\mu(t)} \]枚举 \(o=dt\)，也即是
\[\large= \prod_{o=1}^{\min\{A,B,C\}}\prod_{i=1}^{\left\lfloor\frac{A}{o}\right\rfloor}\prod_{j=1}^{\left\lfloor\frac{B}{o}\right\rfloor}(ijo^2)^{\varphi(o)\left\lfloor\frac{C}{o}\right\rfloor}=\prod_{o=1}^{\min\{A,B,C\}}o^{2\varphi(o)\left\lfloor\frac{A}{o}\right\rfloor\left\lfloor\frac{B}{o}\right\rfloor\left\lfloor\frac{C}{o}\right\rfloor}\prod_{i=1}^{\left\lfloor\frac{A}{o}\right\rfloor}\prod_{j=1}^{\left\lfloor\frac{B}{o}\right\rfloor}(ij)^{\varphi(o)\left\lfloor\frac{C}{o}\right\rfloor} \]\[\large=\left(\prod_{o=1}^{\min\{A,B,C\}}o^{2\varphi(o)\left\lfloor\frac{A}{o}\right\rfloor\left\lfloor\frac{B}{o}\right\rfloor\left\lfloor\frac{C}{o}\right\rfloor}\right)\left(\prod_{o=1}^{\min\{A,B,C\}}\left[\left(\left\lfloor\frac{A}{o}\right\rfloor!\right)^{\left\lfloor\frac{B}{o}\right\rfloor}\left(\left\lfloor\frac{B}{o}!\right\rfloor\right)^{\left\lfloor\frac{A}{o}\right\rfloor}\right]^{\varphi(o)\left\lfloor\frac{C}{o}\right\rfloor}\right) \]分母如果先枚举 \(\gcd(i,j)\) 里面向下取整的式子无法预处理出来，
以 \(\gcd(i,j)\) 为例，不妨先枚举 \(\gcd(i,j,k)\)
\[=\prod_{d=1}^{\min\{A,B,C\}}\prod_{i=1}^{\left\lfloor\frac{A}{d}\right\rfloor}\prod_{j=1}^{\left\lfloor\frac{B}{d}\right\rfloor}\prod_{k=1}^{\left\lfloor\frac{C}{d}\right\rfloor}(d\gcd(i,j))^{d[gcd(i,j,k)==1]} \]\[=\prod_{d=1}^{\min\{A,B,C\}}\prod_{t=1}^{\min\left\{\left\lfloor\frac{A}{d}\right\rfloor,\left\lfloor\frac{B}{d}\right\rfloor,\left\lfloor\frac{C}{d}\right\rfloor\right\}}\prod_{i=1}^{\left\lfloor\frac{A}{dt}\right\rfloor}\prod_{j=1}^{\left\lfloor\frac{B}{dt}\right\rfloor}\prod_{k=1}^{\left\lfloor\frac{C}{dt}\right\rfloor}(\gcd(i,j)dt)^{d\mu(t)} \]枚举 \(o=dt\)，也即是
\[\large= \prod_{o=1}^{\min\{A,B,C\}}\prod_{i=1}^{\left\lfloor\frac{A}{o}\right\rfloor}\prod_{j=1}^{\left\lfloor\frac{B}{o}\right\rfloor}(\gcd(i,j)o)^{\varphi(o)\left\lfloor\frac{C}{o}\right\rfloor} \]实际上由于分子分母都具有 \(\large \prod_{o=1}^{\min\{A,B,C\}}o^{2\varphi(o)\left\lfloor\frac{A}{o}\right\rfloor\left\lfloor\frac{B}{o}\right\rfloor\left\lfloor\frac{C}{o}\right\rfloor}\)（分母上式要算两次）
设 \(\large S3(A,B,C)=\prod_{o=1}^{\min\{A,B,C\}}\prod_{i=1}^{\left\lfloor\frac{A}{o}\right\rfloor}\prod_{j=1}^{\left\lfloor\frac{B}{o}\right\rfloor}{\gcd(i,j)}^{\varphi(o)\left\lfloor\frac{C}{o}\right\rfloor}\)
所以合起来可以进行第一步化简
继续看分母，枚举 \(d=\gcd(i,j)\)
\[\large =\prod_{o=1}^{\min\{A,B,C\}}\prod_{d=1}^{\min\left\{\left\lfloor\frac{A}{o}\right\rfloor,\left\lfloor\frac{B}{o}\right\rfloor,\left\lfloor\frac{C}{o}\right\rfloor\right\}}\prod_{i=1}^{\left\lfloor\frac{A}{od}\right\rfloor}\prod_{j=1}^{\left\lfloor\frac{B}{od}\right\rfloor}d^{\varphi(o)\left\lfloor\frac{C}{o}\right\rfloor[\gcd(i,j)==1]} \]\[\large =\prod_{o=1}^{\min\{A,B,C\}}\prod_{d=1}^{\min\left\{\left\lfloor\frac{A}{o}\right\rfloor,\left\lfloor\frac{B}{o}\right\rfloor,\left\lfloor\frac{C}{o}\right\rfloor\right\}}\prod_{t=1}^{\min\left\{\left\lfloor\frac{A}{od}\right\rfloor,\left\lfloor\frac{B}{od}\right\rfloor,\left\lfloor\frac{C}{od}\right\rfloor\right\}} d^{\varphi(o)\mu(t)\left\lfloor\frac{C}{o}\right\rfloor\left\lfloor\frac{A}{odt}\right\rfloor\left\lfloor\frac{B}{odt}\right\rfloor} \]枚举 \(i=dt\)，则
\[\large =\prod_{o=1}^{\min\{A,B,C\}}\prod_{i=1}^{\min\left\{\left\lfloor\frac{A}{o}\right\rfloor,\left\lfloor\frac{B}{o}\right\rfloor,\left\lfloor\frac{C}{o}\right\rfloor\right\}}{\left(\prod_{d|i}d^{\mu\left(\frac{i}{d}\right)}\right)}^{\varphi(o)\left\lfloor\frac{C}{o}\right\rfloor\left\lfloor\frac{A}{oi}\right\rfloor\left\lfloor\frac{B}{oi}\right\rfloor} \]\[\large =\prod_{o=1}^{\min\{A,B,C\}}\left(\prod_{i=1}^{\min\left\{\left\lfloor\frac{A}{o}\right\rfloor,\left\lfloor\frac{B}{o}\right\rfloor,\left\lfloor\frac{C}{o}\right\rfloor\right\}}f(i)^{\left\lfloor\frac{A}{oi}\right\rfloor\left\lfloor\frac{B}{oi}\right\rfloor}\right)^{\varphi(o)\left\lfloor\frac{C}{o}\right\rfloor} \]那么 \(\large S3(A,B,C)=\prod_{o=1}^{\min\{A,B,C\}}\left(\prod_{i=1}^{\min\left\{\left\lfloor\frac{A}{o}\right\rfloor,\left\lfloor\frac{B}{o}\right\rfloor,\left\lfloor\frac{C}{o}\right\rfloor\right\}}f(i)^{\left\lfloor\frac{A}{oi}\right\rfloor\left\lfloor\frac{B}{oi}\right\rfloor}\right)^{\varphi(o)\left\lfloor\frac{C}{o}\right\rfloor}\)
合起来当 \(type=2\) 时答案为
\[\large =\frac{\prod_{o=1}^{\min\{A,B,C\}}\left[\left(\left\lfloor\frac{A}{o}\right\rfloor!\right)^{\left\lfloor\frac{B}{o}\right\rfloor}\left(\left\lfloor\frac{B}{o}!\right\rfloor\right)^{\left\lfloor\frac{A}{o}\right\rfloor}\right]^{\varphi(o)\left\lfloor\frac{C}{o}\right\rfloor}}{S3(A,B,C)S3(A,C,B)} \]以上需要预处理的函数都可以在 \(O(n\log{n})\) 内预处理出来，瓶颈时间复杂度即求 \(S3(A,B,C)\) 时为 \(O(Tn^{\frac{3}{4}}\log{n})\)
代码
#include
#include
#include
using namespace std;
const int N=100011;
int mu[N],phi[N],fac[N],inv[N],prime[N],c2[N];
int Cnt,f[N],F[N],invf[N],g[N],invF[N],T,mod,Phi;
int iut(){
int ans=0; char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans;
}
void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
int ksm(int x,int y){
int ans=1;
for (;y;y>>=1,x=1ll*x*x%mod)
if (y&1) ans=1ll*ans*x%mod;
return ans;
}
int mo(int x,int y){return x+y>=Phi?x+y-Phi:x+y;}
int min(int a,int b){return a