【Luogu】 P4619 [SDOI2018] 旧试题

题目链接

点击打开链接

题目解法

考虑 $d(ijk)$ 不好求
但我们可以转化 $d(ijk)=\sum _{u|i}\sum _{v|j}\sum _{w|k}[(u,v)=1][(u,w)=1][(v,w)=1]$（我是做这道题的时候才知道这个式子的，但感觉挺有用的）
看到了熟悉的 $\gcd (a,b)=1$ 的形式，然后就可以开始莫比乌斯反演
$$\begin{gathered} Ans=\sum _{i=1}^A\sum _{j=1}^B\sum _{k=1}^C\sum _{u|i}\sum _{v|j}\sum _{w|k}[(u,v)=1][(u,w)=1][(v,w)=1] \\ =\sum _{i=1}^A\sum _{j=1}^B\sum _{k=1}^C\sum _{u|i}\sum _{v|j}\sum _{w|k}\sum _{d1|u,d1|v}\mu (d1)\sum _{d2|u,d2|w}\mu (d2)\sum _{d3|v,d3|w}\mu (d3) \end{gathered}$$
发现枚举 $i,j,k$ 没有必要
所以 $Ans=\sum _{u|i}\sum _{v|j}\sum _{w|k}\lfloor \frac{A}{u}\rfloor \lfloor \frac{B}{v}\rfloor \lfloor \frac{C}{w}\rfloor \sum _{d1|u,d1|v}\mu (d1)\sum _{d2|u,d2|w}\mu (d2)\sum _{d3|v,d3|w}\mu (d3)$
交换循环顺序，先枚举 $d1,d2,d3$
可得 $Ans=\sum _{d1}\mu (d1)\sum _{d2}\mu (d2)\sum _{d3}\mu (d3)\sum _{[u,v]|i}\sum _{[u,w]|j}\sum _{[v,w]|k}\lfloor \frac{A}{u}\rfloor \lfloor \frac{B}{v}\rfloor \lfloor \frac{C}{w}\rfloor$
我们令 $g{A}_i$ 表示 $\sum \lfloor \frac{A}{i}\rfloor +\lfloor \frac{A}{2i}\rfloor +...$，同理我们定义 $g{B}_i$ 和 $g{C}_i$
$gA,gB,gC$ 都是可以用 $O(n\ln n)$ 的时间暴力求出的
所以 $Ans=\sum _{d1}\mu (d1)\sum _{d2}\mu (d2)\sum _{d3}\mu (d3)gA([d1,d2])gB([d1,d3])gC([d2,d3])$
上面的推导感觉很自然

考虑直接枚举 $d1,d2,d3$ 的复杂度仍然很高，但我们可以感受到三元组 $d1,d2,d3$ 的组数不是很大
接下来的一步就很神了
我们把 $i,j$ 之间连边当且仅当 $\mu (i)\ne 0，\mu (j)\ne 0$
我们用暴力跑过之后发现边数最多为 $760741$，是可以接受暴力枚举三元环的 $O(m\sqrt{m})$ 的复杂度的
于是直接建完图之后暴力枚举三元环即可
如何建图？枚举 $gcd(i,j)$，然后就是找到 $(i^{\prime },j^{\prime })=1$ 的对，然后建图
注意考虑 $u=v=w$ 和 $u=v/u=w/v=w$ 的情况
$u=v=w$ 的情况可以直接枚举
$u=v/u=w/v=w$ 的情况可以建图时顺带做一下
时间复杂度 $O(Tm\sqrt{m})$

#include 
#define swap(x,y) x^=y^=x^=y
#define pb push_back
using namespace std;
const int N=200100,P=1e9+7;
typedef long long LL;
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
typedef pair<int,int> pii;
int mu[N];
int gA[N],gB[N],gC[N],deg[N],tag[N];
vector<pii> G[N];
tuple<int,int,int> E[761000];
void work(){
    int A=read(),B=read(),C=read();
    //calc gA
    for(int i=1;i<=A;i++) for(int j=1;j<=A/i;j++) gA[i]+=A/i/j;
    //calc gB
    for(int i=1;i<=B;i++) for(int j=1;j<=B/i;j++) gB[i]+=B/i/j;
    //calc gC
    for(int i=1;i<=C;i++) for(int j=1;j<=C/i;j++) gC[i]+=C/i/j;
    int mn=min(A,min(B,C)),mx=max(A,max(B,C));
    LL ans=0;
    //u=v=w
    for(int d=1;d<=mn;d++) if(mu[d]) ans+=1ll*mu[d]*gA[d]*gB[d]*gC[d];
    int tot=0;
    for(int g=1;g<=mx;g++)
        for(int i=1;i<=mx/g;i++) if(mu[i*g])
            for(int j=i+1;j<=mx/g/i;j++) if(mu[j*g]&&__gcd(i,j)==1){
                //u=v 或 u=w 或 v=w
                ans+=mu[j*g]*(1ll*gA[i*j*g]*gB[i*j*g]*gC[i*g]+1ll*gA[i*j*g]*gB[i*g]*gC[i*j*g]+1ll*gA[i*g]*gB[i*j*g]*gC[i*j*g]);
                ans+=mu[i*g]*(1ll*gA[i*j*g]*gB[i*j*g]*gC[j*g]+1ll*gA[i*j*g]*gB[j*g]*gC[i*j*g]+1ll*gA[j*g]*gB[i*j*g]*gC[i*j*g]);
                deg[i*g]++,deg[j*g]++;
                E[++tot]={i*g,j*g,i*j*g};
            }
    for(int i=1;i<=tot;i++){
        int x=get<0>(E[i]),y=get<1>(E[i]),z=get<2>(E[i]);
        if(deg[x]<deg[y]) swap(x,y);
        G[x].pb({y,z});
    }
    //u,v,w互不相等
    for(int i=1;i<=mx;i++){
        for(auto [j,lcm]:G[i]) tag[j]=lcm;
        for(auto [j,lcm1]:G[i])
            for(auto [k,lcm2]:G[j])
                if(tag[k])
                    ans+=mu[i]*mu[j]*mu[k]*(1ll*gA[lcm1]*gB[lcm2]*gC[tag[k]]+1ll*gA[lcm1]*gB[tag[k]]*gC[lcm2]+
                                            1ll*gA[lcm2]*gB[lcm1]*gC[tag[k]]+1ll*gA[lcm2]*gB[tag[k]]*gC[lcm1]+
                                            1ll*gA[tag[k]]*gB[lcm1]*gC[lcm2]+1ll*gA[tag[k]]*gB[lcm2]*gC[lcm1]);
        for(auto [j,lcm]:G[i]) tag[j]=0;
    }
    printf("%d\n",ans%P);
    for(int i=1;i<=mx;i++) gA[i]=gB[i]=gC[i]=0,G[i].clear(),deg[i]=0;
}
int v[N],pr[N],cnt;
void sieve(int n){
    mu[1]=1;
    for(int i=2;i<=n;i++){
        if(!v[i]) v[i]=i,pr[++cnt]=i,mu[i]=-1;
        for(int j=1;j<=cnt&&pr[j]<=n/i;j++){
            v[pr[j]*i]=pr[j];
            if(v[i]==pr[j]) break;
            mu[pr[j]*i]=-mu[i];
        }
    }
}
int main(){
    sieve(N-1);
    int T=read();
    while(T--) work();
    return 0;
}

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