题目链接

这似乎是SDOI那几道题的强化版?

考虑枚举$i$,并对$(i,j),(i,k)$进行反演(本文用$(x,y)$表示$x,y$的$\gcd$): $$ \begin{aligned} &\sum_{i,j,k}A_iB_jC_kD_{(i,j)}E_{(i,k)}F_{(j,k)}\\ =&\sum_{i,j,k} A_iB_jC_kF_{(j,k)}\sum_{p|(i,j)}(\mu D)_p\sum_{q|(i,k)}(\mu E)_q\\ =&\sum_{p,q}(\mu D)_p(\mu E)_q\sum_{\mathbb{lcm}(p,q)|i}A_i\sum_{p|j}B_j\sum_{q|k}C_kF_{(j,k)}\\ &(记d=(p,q),x=p/d,y=q/d,n'=\lfloor n/d\rfloor,\\ &A'_d=\sum_{d|x,x\leq n}A_x,\\ &D'=\mu D,E'=\mu E)\\ =&\sum_d\sum_{xy\leq n',(x,y)=1}D'_{dx}E'_{dy}A'_{dxy}\sum_{dx|j}\sum_{dy|k}B_jC_kF_{(j,k)} \end{aligned} $$

假设$d,x,y$已经确定,且$x\leq y$,考虑计算后面的求和: $$ \begin{aligned} &\sum_{dx|j}\sum_{dy|k}B_jC_kF_{(j,k)}\\ =&\sum_{j=1}^{n'}\sum_{k=1}^{n'}[x|j,y|k]B_{dj}C_{dk}F_{d(j,k)}\\ =&\sum_{j=1}^{n'}\sum_{k=1}^{n'}[x|j,y|k]B'_jC'_kF'_{(j,k)}\\ =&\sum_{y|k}C'_k\sum_{d|k}(\mu F')_d\sum_{d|j}[x|j]B'_j \end{aligned} $$

我们暴力枚举所有的$d,x$。上面这坨东西只涉及到对因子求和以及对倍数求和,通过枚举质因子,我们可以每次用$O(n/d\log \log n/d)$的时间计算这坨东西对于每个$y$的值。这样复杂度就是$O(\sum_dn/d * \sqrt{n/d}\log \log n/d)=O(n^{1.5}\log \log n)$。中间那个根号是因为每次要在$\sqrt{n/d}$的范围内枚举$x$的取值。$x>y$的情况同理,求和式子里把$j$提到前面,再每次暴力枚举$y$就行了。

#include <bits/stdc++.h>
#define MAXN 100010
#define ULL unsigned long long

ULL read(){
    char c;
    while((c=getchar())<'0' || c>'9');
    ULL res=c-'0';
    while((c=getchar())>='0' && c<='9') res=res*10+c-'0';
    return res;
}

int n,n1;
int p[MAXN],np;
ULL A[MAXN],B[MAXN],C[MAXN],D[MAXN],E[MAXN],F[MAXN];
ULL B1[MAXN],C1[MAXN],F1[MAXN],S[MAXN];

void init(){
    static bool flag[MAXN];
    for(int i=2;i<=n;i++){
        if(!flag[i]) p[++np]=i;
        for(int j=1;j<=np && i*p[j]<=n;j++){
            flag[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
}

//s_x = \sum_{d|x} f_d
void s1(ULL *a,int n){
    for(int i=1;i<=np && p[i]<=n;i++)
        for(int j=p[i],k=1;j<=n;j+=p[i],k++)
            a[j]+=a[k];
}

//s_x = \sum_{x|d} f_d
void s2(ULL *a,int n){
    for(int i=1;i<=np && p[i]<=n;i++)
        for(int j=n/p[i],k=j*p[i];j>=1;j--,k-=p[i])
            a[j]+=a[k];
}

//s_x = \sum_{d|x} \mu(x/d)*f_d
void s3(ULL *a,int n){
    for(int i=1;i<=np && p[i]<=n;i++)
        for(int j=n/p[i],k=j*p[i];j>=1;j--,k-=p[i])
            a[k]-=a[j];
}

int gcd(int x,int y){
    while(y){ int t=x%y; x=y; y=t; }
    return x;
}

void gao_x(int x,ULL *B1,ULL *C1){
    memset(S,0,sizeof(S[0])*(n1+1));
    for(int i=x;i<=n1;i+=x) S[i]=B1[i];
    s2(S,n1);
    for(int i=1;i<=n1;i++) S[i]*=F1[i];
    s1(S,n1);
    for(int i=1;i<=n1;i++) S[i]*=C1[i];
    s2(S,n1);
}

ULL solve_d(int d){
    n1=n/d;
    for(int i=1;i<=n1;i++) B1[i]=B[i*d],C1[i]=C[i*d],F1[i]=F[i*d];
    s3(F1,n1);
    ULL res=0;
    for(int x=1;x*x<=n1;x++){
        gao_x(x,B1,C1);
        for(int y=x;y*x<=n1;y++)
            if(gcd(x,y)==1)
                res+=S[y]*A[d*x*y]*D[d*x]*E[d*y];
    }
    for(int y=1;y*y<=n1;y++){
        gao_x(y,C1,B1);
        for(int x=y+1;y*x<=n1;x++)
            if(gcd(x,y)==1)
                res+=S[x]*A[d*x*y]*D[d*x]*E[d*y];
    }
    return res;
}

int main(){
#ifdef DEBUG
    freopen("2476.in","r",stdin);
#endif
    n=read();
    for(int i=1;i<=n;i++) A[i]=read();
    for(int i=1;i<=n;i++) B[i]=read();
    for(int i=1;i<=n;i++) C[i]=read();
    for(int i=1;i<=n;i++) D[i]=read();
    for(int i=1;i<=n;i++) E[i]=read();
    for(int i=1;i<=n;i++) F[i]=read();
    init();
    s2(A,n);
    s3(D,n); s3(E,n);
    ULL ans=0;
    for(int d=1;d<=n;d++)
        ans+=solve_d(d);
    printf("%llu\n",ans);
    return 0;
}