专栏文章
P14488
P14488题解参与者 2已保存评论 1
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @min9cbs0
- 此快照首次捕获于
- 2025/12/01 22:41 3 个月前
- 此快照最后确认于
- 2025/12/01 22:41 3 个月前
三重求和问题，同时反演三个 ，可以得到 。直接沿用三元环计数做法，因为没有乘 ，很难通过。考虑只反演两个 ：
&\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$：
$$\begin{aligned}&\sum_{u=1}^m\sum_{v=1}^mE'_uF'_vC'_{uv}[\gcd(u,v)=1]\sum_{u\mid i}\sum_{v\mid j}A_iB_jD_{\gcd(i,j)}\\&=\sum_{u=1}^m\sum_{v=1}^mE'_uF'_vC'_{uv}[\gcd(u,v)=1]\sum_{u\mid i}^m\sum_{v\mid j}^mA_iB_j\sum_{w\mid i,w\mid j}D'_w(D'=D\ast\mu)\\&=\sum_{u=1}^m\sum_{v=1}^mE'_uF'_vC'_{uv}[\gcd(u,v)=1]\sum_{v\mid j}B_j\sum_{w\mid j}D'_w\sum_{w\mid i}A_i[u\mid i]
\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)$。
```cpp
#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;
}
```相关推荐
评论
共 1 条评论，欢迎与作者交流。
正在加载评论...