《莫比乌斯反演基础练习题》
时律
·
·
个人记录
然后我们来写幽灵乐团这个史诗级傻逼题。
\prod\limits_{i=1}^A\prod\limits_{j=1}^B\prod\limits_{k=1}^C\left(\dfrac{\operatorname{lcm}(i,j)}{\gcd(i,k)}\right)^{f(type)},f(0)=1,f(1)=ijk,f(2)=\gcd(i,j,k)
type=0
\prod\limits_{i=1}^A\prod\limits_{j=1}^B\prod\limits_{k=1}^C\dfrac{\operatorname{lcm}(i,j)}{\gcd(i,k)}=\dfrac{\left(\prod\limits_{i=1}^A\prod\limits_{j=1}^B\operatorname{lcm}(i,j)\right)^C}{\left(\prod\limits_{i=1}^A\prod\limits_{j=1}^C\operatorname{gcd}(i,j)\right)^B}
其中 \prod\limits_{i=1}^A\prod\limits_{j=1}^B\operatorname{lcm}(i,j)=\prod\limits_{i=1}^A\prod\limits_{j=1}^B\dfrac{ij}{\gcd(i,j)}=\dfrac{(A!)^B(B!)^A}{\prod\limits_{i=1}^A\prod\limits_{j=1}^B\gcd(i,j)}
所以令 f(n,m)=\prod\limits_{i=1}^n\prod\limits_{j=1}^m\gcd(i,j)。答案为 \dfrac{(A!)^{BC}(B!)^{AC}}{f(A,C)^Bf(A,B)^C}
f(n,m)=\prod\limits_{i=1}^n\prod\limits_{j=1}^m\gcd(i,j)=\prod\limits_{k=1}^nk^{\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=k]}=\prod\limits_{k=1}^nk^{\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}[\gcd(i,j)=1]}=\prod\limits_{k=1}^nk^{\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}\sum\limits_{d|i,d|j}\mu(d)}
=\prod\limits_{k=1}^nk^{\sum\limits_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}[d|i]\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}[d|j]}=\prod\limits_{k=1}^nk^{\sum\limits_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)\lfloor\frac{n}{dk}\rfloor\lfloor\frac{m}{dk}\rfloor}=\prod\limits_{T=1}^n\left(\prod\limits_{k|T}k^{\mu(\frac{T}{k})}\right)^{\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor}
然后就可以 O(n \lg n)-O(\sqrt{n}\lg n) 做了。
type=1
\prod\limits_{i=1}^A\prod\limits_{j=1}^B\prod\limits_{k=1}^C\left(\dfrac{\operatorname{lcm}(i,j)}{\gcd(i,k)}\right)^{ijk}=\prod\limits_{i=1}^A\prod\limits_{j=1}^B\prod\limits_{k=1}^C\dfrac{\operatorname{lcm}(i,j)^{ijk}}{\gcd(i,k)^{ijk}}=\dfrac{\left(\prod\limits_{i=1}^A\prod\limits_{j=1}^B\operatorname{lcm}(i,j)^{ij}\right)^{\frac{C(C+1)}{2}}}{\left(\prod\limits_{i=1}^A\prod\limits_{j=1}^C\gcd(i,j)^{ij}\right)^{\frac{B(B+1)}{2}}}
其中 \prod\limits_{i=1}^A\prod\limits_{j=1}^B\operatorname{lcm}(i,j)^{ij}=\dfrac{\prod\limits_{i=1}^A\prod\limits_{j=1}^Bi^{ij}j^{ij}}{\prod\limits_{i=1}^A\prod\limits_{j=1}^B\gcd(i,j)^{ij}}
上面那个就令 s(x)=\prod\limits_{i=1}^xi^i，于是 \prod\limits_{i=1}^A\prod\limits_{j=1}^Bi^{ij}j^{ij}=s(B)^{\frac{A(A+1)}{2}}s(A)^{\frac{B(B+1)}{2}}
所以令 g(n,m)=\prod\limits_{i=1}^n\prod\limits_{j=1}^m\gcd(i,j)^{ij}=\prod\limits_{k=1}^nk^{\sum\limits_{i=1}^n\sum\limits_{j=1}^mij[\gcd(i,j)=k]}=\prod\limits_{k=1}^nk^{k^2\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}ij[\gcd(i,j)=1]}=\prod\limits_{k=1}^nk^{k^2\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}ij\sum\limits_{d|i,d|j}\mu(d)}
=\prod\limits_{k=1}^nk^{k^2\sum\limits_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}i[d|i]\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}j[d|j]}=\prod\limits_{k=1}^nk^{k^2\sum\limits_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)d^2\frac{(1+\lfloor\frac{n}{dk}\rfloor)\lfloor\frac{n}{dk}\rfloor}{2}\frac{(1+\lfloor\frac{m}{dk}\rfloor)\lfloor\frac{m}{dk}\rfloor}{2}}=\prod\limits_{T=1}^n\left(\prod\limits_{k|T}k^{T^2\mu(\frac{T}{k})}\right)^{\frac{(1+\lfloor\frac{n}{T}\rfloor)\lfloor\frac{n}{T}\rfloor(1+\lfloor\frac{m}{T}\rfloor)\lfloor\frac{m}{T}\rfloor}{4}}
然后你又可以 O(n\lg n)-O(\sqrt{n}\lg n) 做了。
type=2
\prod\limits_{i=1}^A\prod\limits_{j=1}^B\prod\limits_{k=1}^C\left(\dfrac{\operatorname{lcm}(i,j)}{\gcd(i,k)}\right)^{\gcd(i,j,k)}=\prod\limits_{i=1}^A\prod\limits_{j=1}^B\prod\limits_{k=1}^C\left(\dfrac{ij}{\gcd(i,j)\gcd(i,k)}\right)^{\gcd(i,j,k)}
所以是相当于求解 t(a,b,c)=\prod\limits_{i=1}^a\prod\limits_{j=1}^b\prod\limits_{k=1}^ci^{\gcd(i,j,k)} 和 h(a,b,c)=\prod\limits_{i=1}^a\prod\limits_{j=1}^b\prod\limits_{k=1}^c\gcd(i,j)^{\gcd(i,j,k)}
答案就是 \dfrac{t(a,b,c)t(b,a,c)}{h(a,b,c)h(a,c,b)}
先考虑 t(a,b,c)=\prod\limits_{i=1}^a\prod\limits_{j=1}^b\prod\limits_{k=1}^ci^{\gcd(i,j,k)}=\prod\limits_{d=1}^{a}\prod\limits_{i=1}^ai^{d\sum\limits_{j=1}^b\sum\limits_{k=1}^c[\gcd(i,j,k)=d]}=\prod\limits_{d=1}^{a}\prod\limits_{i=1}^{\lfloor\frac{a}{d}\rfloor}(id)^{d\sum\limits_{j=1}^{\lfloor\frac{b}{d}\rfloor}\sum\limits_{k=1}^{\lfloor\frac{c}{d}\rfloor}\sum\limits_{t|i,t|j,t|k}\mu(t)}=\prod\limits_{d=1}^{a}\prod\limits_{i=1}^{\lfloor\frac{a}{d}\rfloor}\prod\limits_{t|i}(id))^{d\mu(t)\lfloor\frac{b}{dt}\rfloor\lfloor\frac{c}{dt}\rfloor}
=\prod\limits_{T=1}^a\left(\prod\limits_{d|T}\prod\limits_{i=1}^{\lfloor\frac{a}{d}\rfloor}(id)^{[\frac{T}{d}|i]d\mu(\frac{T}{d})}\right)^{\lfloor\frac{b}{T}\rfloor\lfloor\frac{c}{T}\rfloor}=\prod\limits_{T=1}^a\left(\prod\limits_{d|T}\left(\lfloor\frac{a}{T}\rfloor!T^{\lfloor\frac{a}{T}\rfloor}\right)^{d\mu(\frac{T}{d})}\right)^{\lfloor\frac{b}{T}\rfloor\lfloor\frac{c}{T}\rfloor}=\prod\limits_{T=1}^a\left(\lfloor\frac{a}{T}\rfloor!T^{\lfloor\frac{a}{T}\rfloor}\right)^{\varphi(T)\lfloor\frac{b}{T}\rfloor\lfloor\frac{c}{T}\rfloor}
预处理 T^{\varphi(T)}，你双可以 O(n \lg n) -O(\sqrt{n} \lg n) 了。
另外一个是 h(a,b,c)=\prod\limits_{i=1}^a\prod\limits_{j=1}^b\prod\limits_{k=1}^c\gcd(i,j)^{\gcd(i,j,k)}=\prod\limits_{d=1}^a\prod\limits_{i=1}^a\prod\limits_{j=1}^b\prod\limits_{k=1}^c\gcd(i,j)^{d[\gcd(i,j,k)=d]}
=\prod\limits_{d=1}^a\prod\limits_{i=1}^{\lfloor\frac{a}{d}\rfloor}\prod\limits_{j=1}^{\lfloor\frac{b}{d}\rfloor}(\gcd(i,j)d)^{d\sum\limits_{k=1}^{\lfloor\frac{c}{d}\rfloor}[\gcd(i,j,k)=1]}=\prod\limits_{d=1}^a\prod\limits_{t=1}^{\lfloor\frac{a}{d}\rfloor}\prod\limits_{i=1}^{\lfloor\frac{a}{dt}\rfloor}\prod\limits_{j=1}^{\lfloor\frac{b}{dt}\rfloor}(\gcd(i,j)td)^{d\mu(t)\lfloor\frac{c}{td}\rfloor}
考虑分离成 \left(\prod\limits_{d=1}^a\prod\limits_{t=1}^{\lfloor\frac{a}{d}\rfloor}(td)^{\mu(t)d\lfloor\frac{a}{dt}\rfloor\lfloor\frac{b}{dt}\rfloor\lfloor\frac{c}{dt}\rfloor}\right)\left(\prod\limits_{d=1}^a\prod\limits_{t=1}^{\lfloor\frac{a}{d}\rfloor}\prod\limits_{i=1}^{\lfloor\frac{a}{dt}\rfloor}\prod\limits_{j=1}^{\lfloor\frac{b}{dt}\rfloor}\gcd(i,j)^{d\mu(t)\lfloor\frac{c}{td}\rfloor}\right)
前面那个 =\prod\limits_{T=1}^aT^{\lfloor\frac{a}{T}\rfloor\lfloor\frac{b}{T}\rfloor\lfloor\frac{c}{T}\rfloor\sum\limits_{d|T}d\mu(\frac{T}{d})}=\prod\limits_{T=1}^aT^{\lfloor\frac{a}{T}\rfloor\lfloor\frac{b}{T}\rfloor\lfloor\frac{c}{T}\rfloor\varphi(T)}
这个可以用前面那个 T^{\varphi(T)}，你叒可以 O(n\lg n)-O(\sqrt{n}\lg n) 了。
后面那个 =\prod\limits_{d=1}\prod\limits_{t=1}\prod\limits_{x=1}x^{d\mu(t)\lfloor\frac{c}{td}\rfloor\sum\limits_{i=1}^{\lfloor\frac{a}{dt}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{b}{dt}\rfloor}[\gcd(i,j)=x]}=\prod\limits_{d=1}\prod\limits_{t=1}\prod\limits_{x=1}x^{d\mu(t)\lfloor\frac{c}{td}\rfloor\sum\limits_{i=1}^{\lfloor\frac{a}{dtx}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{b}{dtx}\rfloor}\sum\limits_{y|i,y|j}\mu(y)}=\prod\limits_{d=1}\prod\limits_{t=1}\prod\limits_{x=1}\prod\limits_{y=1}x^{d\mu(t)\mu(y)\lfloor\frac{c}{td}\rfloor\lfloor\frac{a}{tdxy}\rfloor\lfloor\frac{b}{tdxy}\rfloor}
=\prod\limits_{T=1}\left(\prod\limits_{U=1}\left(\prod\limits_{d|U}d^{\mu(\frac{U}{d})}\right)^{\lfloor\frac{a}{TU}\rfloor\lfloor\frac{b}{TU}\rfloor}\right)^{\varphi(T)\lfloor\frac{c}{T}\rfloor}
所以你叕可以 O(n \lg n) -……哦，这回询问是两层数论分块所以是 O(n^{\frac{3}{4}}\lg n) 了。
最后整理一下需要预处理一些什么：
抽象至极，不是吗。
柿子大概推了两三个小时，~~期间终于过了 5dan 的技叠乱但是仍然不会切~~，代码大概写了半小时。
```cpp
//Private Eye,dancing with the wind.
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
const int maxn=100000;
int MOD;
int prime[MAXN],mu[MAXN],phi[MAXN],sumphi[MAXN],cnt;
int inv[MAXN],fac[MAXN],s1[MAXN],inv1[MAXN],s2[MAXN],s3[MAXN],inv3[MAXN],s4[MAXN],inv4[MAXN];
bitset<MAXN> v;
inline int qpow(int x,int k)
{
int res=1;
while(k)
{
if(k&1) res=1ll*res*x%MOD;
x=1ll*x*x%MOD;
k>>=1;
}
return res;
}
inline void init()
{
inv[0]=fac[0]=mu[1]=phi[1]=1;
for(int i=1;i<=maxn;i++) inv[i]=qpow(i,MOD-2),fac[i]=1ll*fac[i-1]*i%MOD;
for(int i=2;i<=maxn;i++)
{
if(!v[i]) prime[++cnt]=i,mu[i]=-1,phi[i]=i-1;
for(int j=1;j<=cnt and i*prime[j]<=maxn;j++)
{
v[i*prime[j]]=1,phi[i*prime[j]]=phi[i]*phi[prime[j]];
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else mu[i*prime[j]]=-mu[i];
}
}
for(int i=1;i<=maxn;i++) sumphi[i]=(sumphi[i-1]+phi[i])%(MOD-1);
s1[0]=inv1[0]=s2[0]=s3[0]=inv3[0]=s4[0]=inv4[0]=1;
for(int i=1;i<=maxn;i++)
{
s2[i]=1ll*s2[i-1]*qpow(i,i)%MOD;
s4[i]=1ll*s4[i-1]*qpow(i,phi[i])%MOD;
inv4[i]=qpow(s4[i],MOD-2);
}
for(int i=1;i<=maxn;i++) s1[i]=1;
for(int i=1;i<=maxn;i++)
for(int j=1;j<=maxn/i;j++)
{
if(mu[j]==1) s1[i*j]=1ll*s1[i*j]*i%MOD;
if(mu[j]==-1) s1[i*j]=1ll*s1[i*j]*inv[i]%MOD;
}
for(int i=1;i<=maxn;i++)
{
s3[i]=1ll*qpow(s1[i],1ll*i*i%(MOD-1))%MOD*s3[i-1]%MOD;
inv3[i]=qpow(s3[i],MOD-2);
s1[i]=1ll*s1[i-1]*s1[i]%MOD;
inv1[i]=qpow(s1[i],MOD-2);
}
}
inline int f(int n,int m)
{
if(n>m) swap(n,m);
int ans=1;
for(int l=1,r;l<=n;l=r+1)
{
r=min(n/(n/l),m/(m/l));
ans=1ll*ans*qpow(1ll*s1[r]*inv1[l-1]%MOD,1ll*(n/l)*(m/l)%(MOD-1))%MOD;
}
return ans;
}
inline int solve0(int a,int b,int c)
{
int ans=1ll*qpow(fac[a],1ll*b*c%(MOD-1))*qpow(fac[b],1ll*a*c%(MOD-1))%MOD;
return 1ll*ans*qpow(f(a,c),MOD-1-b)%MOD*qpow(f(a,b),MOD-1-c)%MOD;
}
inline int g(int n,int m)
{
if(n>m) swap(n,m);
int ans=1;
for(int l=1,r;l<=n;l=r+1)
{
r=min(n/(n/l),m/(m/l));
ans=1ll*ans*qpow(1ll*s3[r]*inv3[l-1]%MOD,1ll*(1ll*(1+n/l)*(n/l)/2%(MOD-1))*(1ll*(1+m/l)*(m/l)/2%(MOD-1))%(MOD-1))%MOD;
}
return ans;
}
inline int solve1(int a,int b,int c)
{
int ans=1ll*qpow(1ll*qpow(s2[b],1ll*a*(a+1)/2%(MOD-1))*qpow(s2[a],1ll*b*(b+1)/2%(MOD-1))%MOD,1ll*c*(c+1)/2%(MOD-1));
return 1ll*ans*qpow(g(a,c),1ll*(MOD-2)*(1ll*b*(b+1)/2%(MOD-1))%(MOD-1))%MOD*qpow(g(a,b),1ll*(MOD-2)*(1ll*c*(c+1)/2%(MOD-1))%(MOD-1))%MOD;
}
inline int t(int a,int b,int c)
{
int ans=1;
for(int l=1,r;l<=min({a,b,c});l=r+1)
{
r=min({a/(a/l),b/(b/l),c/(c/l)});
ans=1ll*ans*qpow(1ll*s4[r]*inv4[l-1]%MOD,1ll*(a/l)*(b/l)%(MOD-1)*(c/l)%(MOD-1))%MOD;
ans=1ll*ans*qpow(fac[a/l],1ll*(b/l)*(c/l)%(MOD-1)*(sumphi[r]-sumphi[l-1]+MOD-1)%(MOD-1))%MOD;
}
return ans;
}
inline int h(int a,int b,int c)
{
int ans=1;
for(int l=1,r;l<=min({a,b,c});l=r+1)
{
r=min({a/(a/l),b/(b/l),c/(c/l)});
ans=1ll*ans*qpow(1ll*s4[r]*inv4[l-1]%MOD,1ll*(a/l)*(b/l)%(MOD-1)*(c/l)%(MOD-1))%MOD;
}
for(int l=1,r;l<=min({a,b,c});l=r+1)
{
r=min({a/(a/l),b/(b/l),c/(c/l)});
int res=1,n=a/l,m=b/l;
for(int L=1,R;L<=min(n,m);L=R+1)
{
R=min(n/(n/L),m/(m/L));
res=1ll*res*qpow(1ll*s1[R]*inv1[L-1]%MOD,1ll*(n/L)*(m/L)%(MOD-1))%MOD;
}
ans=1ll*ans*qpow(res,1ll*(c/l)*(sumphi[r]-sumphi[l-1]+MOD-1)%(MOD-1))%MOD;
}
return ans;
}
inline int solve2(int a,int b,int c)
{
return 1ll*t(a,b,c)*t(b,a,c)%MOD*qpow(h(a,b,c),MOD-2)%MOD*qpow(h(a,c,b),MOD-2)%MOD;
}
int main()
{
int T;
scanf("%d%d",&T,&MOD);
init();
while(T--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
printf("%d %d %d\n",solve0(a,b,c),solve1(a,b,c),solve2(a,b,c));
}
}
```