LOJ #2476. 「2018 集训队互测 Day 3」蒜头的奖杯（三元环计数）

题目 泰勒应天下大雨！ 类似于$SDOI2018$旧试题。 给$D$,$E$,$F$卷上$\mu$。 得到$D^{\prime },E^{\prime },F^{\prime }$。 原式变为$$\sum _{i,j,k}{A}_i{B}_j{C}_k\sum _{a|i,a|j}{D}_a^{\prime }\sum _{b|i,b|k}{E}_b^{\prime }\sum _{c|j,c|k}{F}_c^{\prime }$$ 交换和号： $$\sum _{a,b,c}{D}_a^{\prime }{E}_b^{\prime }{F}_c^{\prime }\sum _{\mathrm{lcm}(a,b)|i,\mathrm{lcm}(a,c)|j,\mathrm{lcm}(b,c)|k}{A}_i,B_j,C_k$$ 给$A,B,C$做一个变换如括号中所述（$A_i^{\prime }={\sum }_{i|d}{A}_d$） 得到$A^{\prime },B^{\prime },C^{\prime }$。 则原式变为${\sum }_{a,b,c}{D}_a^{\prime }{E}_b^{\prime }{F}_c^{\prime }{A}_{\mathrm{lcm}(a,b)}^{\prime }{B}_{\mathrm{lcm}(a,c)}^{\prime }{C}_{\mathrm{lcm}(b,c)}^{\prime }$ 所以我们就对于${\mathrm{lcm}}_{a,b}\le n$的$a,b$连边求三元环计数（注意这里是有边权有点权的三元环权值计数，权值为点权和边权六个的乘积。） 随便跑了一下最大数据发现有$m=2625630$ 条边。 写一个三元环计数即可在$O(m\sqrt{m})$的复杂度解决此题。 虽然和标程$n\sqrt{n}\log \log n$比起来感觉有点不优秀（$2e6$的$m\sqrt{m}$也挺吓人的，本机不开$-O2$跑了$10s$。） 但是在$LOJ$的实际表现是差不多的。 $\mathcal{A}CCode$

#include<bits/stdc++.h> #define maxn 100005 #define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++) #define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--) #define LL long long #define pii pair<int,LL> #define mp make_pair #define vi vector<pair<int,LL> > #define pb emplace_back using namespace std; char cb[1<<16],*cs=cb,*ct=cb; #define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<16,stdin),cs==ct)?0:*cs++) template<class T>void read(T &res){ char ch; for(;!isdigit(ch=getc());); for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0'); } int n,mu[maxn],pr[maxn],cnt_pr,vis[maxn],in[maxn]; LL A[6][maxn],B[6][maxn],ans; int gcd(int a,int b){ return !b ? a : gcd(b,a%b); } void upd(int a,int b,int c,int lab,int lbc,int lac){ ans += B[0][lab] * B[1][lac] * B[2][lbc] * B[3][a] * B[4][b] * B[5][c] + (a != b ? B[0][lab] * B[1][lbc] * B[2][lac] * B[3][b] * B[4][a] * B[5][c] : 0) + (b != c ? B[0][lac] * B[1][lab] * B[2][lbc] * B[3][a] * B[4][c] * B[5][b] : 0) + (a != c ? B[0][lbc] * B[1][lac] * B[2][lab] * B[3][c] * B[4][b] * B[5][a] : 0) + (a != b && b != c && a != c ? B[0][lbc] * B[1][lab] * B[2][lac] * B[3][b] * B[4][c] * B[5][a] + B[0][lac] * B[1][lbc] * B[2][lab] * B[3][c] * B[4][a] * B[5][b] : 0); } vi G[maxn],E[maxn]; int tim; LL cst[maxn]; int main(){ read(n); rep(t,0,5) rep(i,1,n) read(A[t][i]); rep(t,0,2) rep(i,1,n) for(int k=i;k<=n;k+=i) B[t][i] += A[t][k]; mu[1] = 1; rep(i,2,n){ if(!vis[i]) pr[cnt_pr++] = i , mu[i] = -1; for(int j=0;pr[j] * i <= n;j++){ vis[i * pr[j]] = 1; if(i % pr[j]) mu[i * pr[j]] = -mu[i]; else{ mu[i * pr[j]] = 0; break; } } } memset(vis,0,sizeof vis); rep(t,3,5) rep(i,1,n) for(int k=i,p=1;k<=n;k+=i,p++) B[t][k] += A[t][i] * mu[p]; rep(i,1,n) upd(i,i,i,i,i,i); rep(i,1,n){ static int ar[maxn]={},cnt,t; cnt = 0; for(int j=i;j<=n;j+=i) ar[++cnt] = j; rep(j,1,cnt) for(int k=1;k<j && (t = ar[j] / i * ar[k]) <= n;k++) if(gcd(ar[j] , ar[k]) == i){ int x = ar[j] , y = ar[k]; upd(x,x,y,x,t,t); upd(y,y,x,y,t,t); in[x] ++ , in[y] ++; G[x].pb(mp(y,t)); } } rep(i,1,n) for(auto v:G[i]) if(in[i] < in[v.first]) E[i].pb(v); else E[v.first].pb(mp(i,v.second)); rep(i,1,n){ ++tim; for(auto v:E[i]) vis[v.first] = tim , cst[v.first] = v.second; for(auto v:E[i]) for(auto p:E[v.first]) if(vis[p.first] == tim) upd(i,v.first,p.first,v.second,p.second,cst[p.first]); } printf("%llu",(unsigned long long)ans); }