P14488

· · 题解

三重求和问题，同时反演三个 \gcd，可以得到 \sum_{u=1}^n\sum_{v=1}^n\sum_{w=1}^n(D\ast\mu)_u(E\ast\mu)_v(F\ast\mu)_w\sum_{u\mid i,v\mid i}A_i\sum_{u\mid j,w\mid j}B_j\sum_{v\mid k,w\mid k}C_k。直接沿用三元环计数做法，因为没有乘 \mu，很难通过。考虑只反演两个 \gcd：

&\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^nA_iB_jC_kD_{\gcd(i,j)}E_{\gcd(i,k)}F_{\gcd(j,k)}\\&=\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^nA_iB_jC_kD_{\gcd(i,j)}\sum_{u\mid i,u\mid k}\sum_{v\mid j,v\mid k}E'_uF'_v(E'=E\ast\mu,F'=F\ast\mu)\\ &=\sum_{u=1}^n\sum_{v=1}^nE'_uF'_vC'_{\operatorname{lcm}(u,v)}\sum_{u\mid i}\sum_{v\mid j}A_iB_jD_{\gcd(i,j)}(C'_i=\sum_{d\mid i}C_i) \end{aligned}

此时即使我们枚举了 u,v，后面的部分仍然难做，考虑继续枚举 \gcd(u,v)：

\begin{aligned}&\sum_{u=1}^n\sum_{v=1}^nE'_uF'_vC'_{\operatorname{lcm}(u,v)}\sum_{u\mid i}\sum_{v\mid j}A_iB_jD_{\gcd(i,j)}\\&=\sum_{d=1}^n\sum_{d\mid u}\sum_{d\mid v}E'_uF'_vC'_{\frac{uv}d}[\gcd(u,v)=d]\sum_{u\mid i}\sum_{v\mid j}A_iB_jD_{\gcd(i,j)}\\&=\sum_{d=1}^n\sum_{u=1}^{\lfloor\frac nd\rfloor}\sum_{v=1}^{\lfloor\frac nd\rfloor}E'_{ud}F'_{vd}C'_{uvd}[\gcd(u,v)=1]\sum_{u\mid i}^{\lfloor\frac nd\rfloor}\sum_{v\mid j}^{\lfloor\frac nd\rfloor}A_{id}B_{jd}D_{d\gcd(i,j)}\end{aligned}

枚举 d，将 d 的倍数位置提取出来。设 m=\lfloor\frac nd\rfloor：

\end{aligned}

因为 uv\leq m，可以想到分为 u<v,u>v,u=v，不妨设 u<v，则 u<\sqrt m。固定 u，后三个求和号可以在 O(m\log\log m) 的时间内做两次狄利克雷后缀和、一次狄利克雷前缀和求得，从而对 v 求和。u>v 时枚举 v，过程类似。u=v 时 u=v=1 是平凡的。因此子问题可以 O(m\sqrt m\log\log m) 解决。总复杂度 O(\sum_{i=1}^n(\frac ni)\sqrt{\frac ni}\log\log i)=O(n\sqrt n\log\log n)。 

#include<bits/stdc++.h>
using namespace std;
int n,prime[100005],cnt;
unsigned long long ta[100005],tb[100005],tc[100005],td[100005],te[100005],tf[100005],a[100005],b[100005],c[100005],d[100005],e[100005],f[100005],t1[100005],t2[100005],ans;
bool vis[100005];
int prime_init(int n,int prime[],bool a[],int cnt=0){
  for(int i=2;i<=n;i++)a[i]=1;
  for(int i=2;i<=n;i++){
    if(a[i])prime[++cnt]=i;
    for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
      a[i*prime[j]]=0;
      if(i%prime[j]==0)break;
    }
  }
  return cnt;
}
void solve(int m){
  for(int i=1;i<=cnt&&prime[i]<=m;i++)for(int j=m/prime[i];j>=1;j--)d[prime[i]*j]-=d[j];
  for(int u=1;u*u<=m;u++){
    for(int i=1;i<=m;i++)t1[i]=i%u?0:a[i],t2[i]=i%u?0:b[i];
    for(int i=1;i<=cnt&&prime[i]<=m;i++)for(int j=m/prime[i];j>=1;j--)t1[j]+=t1[prime[i]*j],t2[j]+=t2[prime[i]*j];
    for(int i=1;i<=m;i++)t1[i]*=d[i],t2[i]*=d[i];
    for(int i=1;i<=cnt&&prime[i]<=m;i++)for(int j=1;j<=m/prime[i];j++)t1[prime[i]*j]+=t1[j],t2[prime[i]*j]+=t2[j];
    for(int i=1;i<=m;i++)t1[i]*=b[i],t2[i]*=a[i];
    for(int i=1;i<=cnt&&prime[i]<=m;i++)for(int j=m/prime[i];j>=1;j--)t1[j]+=t1[prime[i]*j],t2[j]+=t2[prime[i]*j];
    for(int v=u+1;u*v<=m;v++)if(__gcd(u,v)==1)ans+=e[u]*f[v]*c[u*v]*t1[v]+e[v]*f[u]*c[u*v]*t2[v];
  }
  for(int i=1;i<=cnt&&prime[i]<=m;i++)for(int j=m/prime[i];j>=1;j--)a[j]+=a[prime[i]*j],b[j]+=b[prime[i]*j];
  for(int i=1;i<=m;i++)ans+=e[1]*f[1]*c[1]*d[i]*a[i]*b[i];
}
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cin>>n,cnt=prime_init(n,prime,vis);
  for(int i=1;i<=n;i++)cin>>ta[i];
  for(int i=1;i<=n;i++)cin>>tb[i];
  for(int i=1;i<=n;i++)cin>>tc[i];
  for(int i=1;i<=n;i++)cin>>td[i];
  for(int i=1;i<=n;i++)cin>>te[i];
  for(int i=1;i<=n;i++)cin>>tf[i];
  for(int i=1;i<=cnt;i++)for(int j=n/prime[i];j>=1;j--)te[prime[i]*j]-=te[j],tf[prime[i]*j]-=tf[j];
  for(int i=1;i<=cnt;i++)for(int j=n/prime[i];j>=1;j--)tc[j]+=tc[prime[i]*j];
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n/i;j++)a[j]=ta[i*j],b[j]=tb[i*j],c[j]=tc[i*j],d[j]=td[i*j],e[j]=te[i*j],f[j]=tf[i*j];
    solve(n/i);
  }
  return cout<<ans<<'\n',0;
}