【Luogu】 P4619 [SDOI2018] 旧试题

试题"/>

【Luogu】 P4619 [SDOI2018] 旧试题

题目链接

点击打开链接

题目解法

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

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

#include <bits/stdc++.h>
#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 gAfor(int i=1;i<=A;i++) for(int j=1;j<=A/i;j++) gA[i]+=A/i/j;//calc gBfor(int i=1;i<=B;i++) for(int j=1;j<=B/i;j++) gB[i]+=B/i/j;//calc gCfor(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=wfor(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=wans+=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;
}