Wuyanru's blog
0%

[MtOI2019] 幽灵乐团/莫比乌斯反演基础练习题

发表于 分类于 ，

一道毒瘤题目，题目链接：luoguP5518。

题意

题目大意：求 。

其中 ，。

题解

让我们先来颓一下柿子。

实际上只需要知道 和 的求法就可以了。

所以我们一共要推 个式子。

type=0

直接看被乘了多少次

枚举质数找注意有的有多个相同质数

第一个式子直接预处理阶乘，然后算 次方。

第二个式子可以通过预处理筛出 ，然后快速幂。

如果想要更快可以筛出所有 的前缀积，然后数论分块。

type=1

和上面一样的方法

第二个式子计算方式和type=0差不多，第一个式子只需要预处理 的前缀积即可。

type=2

令然后枚举莫比乌斯反演将提前枚举

枚举

然后你就会发现分子的右边的式子和分母的左边的式子约掉了。

于是我们现在只需要求 和 。

第一个式子只需要预处理阶乘、 的前缀和，然后就可以分块。

第二个式子还需要推一推。 枚举

然后你会发现 是可以预处理的。

于是乎，两遍整除分块就可以了。

最终时间复杂度是 的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include<algorithm>
#include<cstdio>
#include<map>
using namespace std;
using ll=long long;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
int mod;
ll qow(ll a,int b)
{
    b=(b%(mod-1)+mod-1)%(mod-1);
    a%=mod;
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
map<int,ll>jyh[100001];
ll prephi[100001];
int pri[100001];
bool is[100001];
int phi[100001];
int pm[100001];
int mu[100001];
ll jc1[100001];
ll jc2[100001];
ll d1[100001];
ll d2[100001];
int A,B,C;
inline ll f(int i){ return 1ll*i*(i+1)/2%(mod-1);}
inline ll get2(int A,int B)
{
    ll ans=jyh[A][B];
    if(ans) return ans;
    ans=1;
    int E=min(A,B);
    for(int lTp=1,rTp;lTp<=E;lTp=rTp+1)
    {
        rTp=min(A/(A/lTp),B/(B/lTp));
        ll val=d1[rTp]*d2[lTp-1]%mod;
        ans=ans*qow(val,(ll)(A/lTp)*(B/rTp)%(mod-1))%mod;
    }
    return jyh[A][B]=ans;
}
inline ll get1(int A,int B,int C)
{
    ll ans=1;
    int D=min(min(A,B),C);
    for(int lT=1,rT;lT<=D;lT=rT+1)
    {
        rT=min(min(A/(A/lT),B/(B/lT)),C/(C/lT));
        ans=ans*qow(get2(A/lT,B/lT),(prephi[rT]-prephi[lT-1])%(mod-1)*(C/lT)%(mod-1))%mod
               *qow(get2(A/lT,C/lT),(prephi[rT]-prephi[lT-1])%(mod-1)*(B/lT)%(mod-1))%mod;
    }
    return ans;
}
inline ll get3(int A,int B,int C)
{
    ll ans=1;
    for(int lT=1,rT;lT<=A&&lT<=B&&lT<=C;lT=rT+1)
    {
        rT=min(min(A/(A/lT),B/(B/lT)),C/(C/lT));
        ans=ans*qow(jc1[A/lT],(prephi[rT]-prephi[lT-1])%(mod-1)*(B/lT)*(C/lT)%(mod-1))%mod;
    }
    return ans;
}
int main()
{
    int t=read(),n=100000;mod=read();
    mu[1]=phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!is[i]) pri[++pri[0]]=i,mu[i]=-1,phi[i]=i-1;
        for(int j=1;j<=pri[0]&&i*pri[j]<=n;j++)
        {
            is[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            mu[i*pri[j]]=-mu[i];
            phi[i*pri[j]]=phi[i]*(pri[j]-1);
        }
    }
    for(int i=1;i<=pri[0];i++) for(ll j=pri[i];j<=n;j*=pri[i]) pm[j]=pri[i];
    jc1[0]=jc2[0]=d1[0]=d2[0]=1;
    for(int i=1;i<=n;i++)
    {
        d1[i]=1;
        prephi[i]=prephi[i-1]+phi[i];
        jc1[i]=jc1[i-1]*i%mod;
        jc2[i]=jc2[i-1]*qow(i,i)%mod;
    }
    for(int i=1;i<=n;i++) for(int j=i;j<=n;j+=i)
        d1[j]=d1[j]*qow(i,mu[j/i])%mod;
    for(int i=2;i<=n;i++) d1[i]=(d1[i]*d1[i-1])%mod;
    for(int i=1;i<=n;i++) d2[i]=qow(d1[i],mod-2);
    while(t--)
    {
        A=read(),B=read(),C=read();
        ll ans=1,val=1;



        ans=ans*qow(jc1[A],1ll*B*C%(mod-1))%mod;
        ans=ans*qow(jc1[B],1ll*A*C%(mod-1))%mod;
        for(int i=1;i<=A&&i<=B;i++) if(pm[i])
            val=val*qow(pm[i],1ll*(A/i)*(B/i)%(mod-1))%mod;
        val=qow(val,C);
        ans=ans*qow(val,mod-2)%mod,val=1;
        for(int i=1;i<=A&&i<=C;i++) if(pm[i])
            val=val*qow(pm[i],1ll*(A/i)*(C/i)%(mod-1))%mod;
        val=qow(val,B);
        ans=ans*qow(val,mod-2)%mod,val=1;
        printf("%lld ",ans),ans=1;



        ans=ans*qow(jc2[A],f(B)*f(C)%(mod-1))%mod;
        ans=ans*qow(jc2[B],f(A)*f(C)%(mod-1))%mod;
        for(int i=1;i<=A&&i<=B;i++) if(pm[i])
            val=val*qow(pm[i],f(A/i)*f(B/i)%(mod-1)*i%(mod-1)*i%(mod-1))%mod;
        val=qow(val,f(C));
        ans=ans*qow(val,mod-2)%mod,val=1;
        for(int i=1;i<=A&&i<=C;i++) if(pm[i])
            val=val*qow(pm[i],f(A/i)*f(C/i)%(mod-1)*i%(mod-1)*i%(mod-1))%mod;
        val=qow(val,f(B));
        ans=ans*qow(val,mod-2)%mod,val=1;
        printf("%lld ",ans),ans=1;



        ans=qow(get1(A,B,C),mod-2);
        ans=ans*get3(A,B,C)%mod*get3(B,A,C)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}