傳送門

Description

\[ \sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^Cd(ijk) (\mathrm{mod\:} 10^9+7) \]

其中 \(d(ijk)\) 表示 \(i × j × k\)的約數個數。

Solution

首先，有一個公式
\[ σ_0(n_1n_2···n_m) =\sum_{a_1|n_1}\sum_{a_2|n_2}···\sum_{a_m|n_m}\prod_{1≤i \neq j≤m} [a_i ⊥ a_j] \]
所以，我們就可以把答案反演成：
\[ \sum_{u=1}^{M}\sum_{v=1}^{M}\sum_{w=1}^{M}\mu(u)\mu(v)\mu(w)\left ( \sum_{lcm(u,v)|x}\frac{A}{x} \right )\left ( \sum_{lcm(v,w)|y}\frac{B}{y} \right )\left ( \sum_{lcm(u,w)|z}\frac{C}{z} \right ) \]
其中,\(M=max\{ A,B,C\}\)

我們發現，根據調和級數，可以求出后面的那些都可以通過\(O(n\log n)\)預處理出來

我們先直接計算\(u=v=w\)以及\(u,v,w\)中恰有兩個數相等的情況

然后剩下的就是\(u,v,w\)互不相同的了，我們把\(lcm(u,v)\leq M\)的\(u,v\)連邊，這樣，其實就是求所有三元環的貢獻啦。

關于求三元環呢，這里有個不常用的黑科技，參見這里,可以使得復雜度為\(O(m\sqrt m)\)

其實圖的邊數是比較少的，所以目測能過

據說用\(vector\)要比較快？

Code?

#include<bits/stdc++.h> #define ll long long #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) inline int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return x*f; } #define MN 200005 #define mN 100005 #define mod 1000000007 int mu[mN],pr[mN/10],tot;bool mark[mN]; int gcd(int x,int y){return y?gcd(y,x%y):x;} inline void init_mu() {mu[1]=1;register int i,j;for(i=2;i<mN;++i){if(!mark[i]){pr[++tot]=i;mu[i]=-1;}for(j=1;j<=tot&&pr[j]*i<mN;++j){mark[pr[j]*i]=true;if(i%pr[j]) mu[pr[j]*i]=-mu[i];else{mu[pr[j]*i]=0;break;}}} } int T,A,B,C,N,M; ll fa[MN],fb[MN],fc[MN],ans; struct edge{int to,lcm;}; struct Edge{int f,t,lcm;}e[MN<<4];int en; std::vector<edge> G[mN]; int d[mN],mrk[mN]; inline void init() {register int i,j;N=max(A,max(B,C));M=min(A,min(B,C));memset(d,0,sizeof d);en=0;for(i=1;i<=N;++i)G[i].clear();ans=0;memset(fa,0,sizeof fa);memset(fb,0,sizeof fb);memset(fc,0,sizeof fc);for(i=1;i<=A;++i) for(j=i;j<=A;j+=i) fa[i]+=A/j;for(i=1;i<=B;++i) for(j=i;j<=B;j+=i) fb[i]+=B/j;for(i=1;i<=C;++i) for(j=i;j<=C;j+=i) fc[i]+=C/j; }#define C(x,y,z) (fa[x]*fb[y]*fc[z]) #define cal(x,y,z) (C(x,y,z)+C(x,z,y)+C(y,x,z)+C(y,z,x)+C(z,x,y)+C(z,y,x))int main() {register int g,i,j,k,x,y,w;T=read();init_mu();while(T--){A=read();B=read();C=read();init();for(i=1;i<=M;++i)if(mu[i])ans+=mu[i]*mu[i]*mu[i]*fa[i]*fb[i]*fc[i];for(g=1;g<=N;++g)for(i=1;i*g<=N;++i)if(mu[i*g])for(j=i+1;1ll*i*j*g<=N;++j)if(mu[j*g]&&gcd(i,j)==1){x=i*g;y=j*g;++d[x];++d[y];e[++en]=(Edge){x,y,x*j};w=x*j;ans+=1ll*mu[x]*mu[x]*mu[y]*(fa[x]*fb[w]*fc[w]+fa[w]*fb[x]*fc[w]+fa[w]*fb[w]*fc[x]);ans+=1ll*mu[x]*mu[y]*mu[y]*(fa[y]*fb[w]*fc[w]+fa[w]*fb[y]*fc[w]+fa[w]*fb[w]*fc[y]);}for(i=1;i<=en;++i)if(d[e[i].f]>d[e[i].t]||(d[e[i].f]==d[e[i].t]&&e[i].f<e[i].t)) G[e[i].f].push_back((edge){e[i].t,e[i].lcm});else G[e[i].t].push_back((edge){e[i].f,e[i].lcm});for(i=1;i<=N;++i){for(j=G[i].size()-1;~j;--j) mrk[G[i][j].to]=G[i][j].lcm;for(j=G[i].size()-1;~j;--j){x=G[i][j].to;register int ix=G[i][j].lcm,iy;for(k=G[x].size()-1;~k;--k)if(iy=mrk[y=G[x][k].to]){register int xy=G[x][k].lcm;ans+=mu[i]*mu[x]*mu[y]*cal(ix,iy,xy);}}for(j=G[i].size()-1;~j;--j) mrk[G[i][j].to]=0;}printf("%lld\n",ans%mod);} }

---

Blog來自PaperCloud，未經允許，請勿轉載，TKS！

轉載于:https://www.cnblogs.com/PaperCloud/p/10280169.html

總結

以上是生活随笔為你收集整理的[bzoj 5332][SDOI2018]旧试题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。