题目链接
题目大意：给定(n,A,B,C,D,E,F)，求$$sum_{i=1}^nsum_{j=1}^nsum_{k=1}^nA_iB_jC_kD_{gcd(i,j)}E_{gcd(i,k)}F_{gcd(j,k)}$$
首先容易想到三个同时算的方法：对(D,E,F)进行反演，得
[sum_{i=1}^nA_isum_{p|i}D_psum_{p|j}^nB_jsum_{r|j}F_rsum_{r|k}^nC_ksum_{q|k}E_q[i\%q=0]
]
设数组(tmp)初始值为(A)，可以先变换再与一个函数对应位置相乘，进行(5)次。要分别对(1 ext{~}n)的每一个起始位置算一次，(O(n^2log n))，喜提TLE。
三个同时算不好算，考虑拆开算，原式即$$sum_{i=1}^nsum_{j=1}^nA_iB_jD_{gcd(i,j)}sum_{k=1}^nC_kE_{gcd(i,k)}F_{gcd(j,k)}$$
同时对(E)和(F)进行莫比乌斯反演得$$sum_{i=1}^nsum_{j=1}^nA_iB_jD_{gcd(i,j)}sum_{k=1}^nC_ksum_{q|i,q|k}E_qsum_{r|j,r|k}F_r$$
于是，根据套路，将被拆开的(C,E,F)提到前面，再提出下标的(gcd)
[egin{align}
&;;;;sum_{i=1}^nsum_{j=1}^nA_iB_jD_{gcd(i,j)}sum_{k=1}^nC_ksum_{q|i,q|k}E_qsum_{r|j,r|k}F_r\
&=sum_{k=1}^nC_ksum_{q|k}E_qsum_{r|k}F_rsum_{i=1}^{lfloorfrac nq
floor}sum_{j=1}^{lfloorfrac nr
floor}A_{iq}B_{jr}D_{gcd(iq,jr)}\
&=sum_{s=1}^nsum_{q=1}^{lfloorfrac ns
floor}sum_{r=1}^{lfloorfrac n{sq}
floor}[gcd(q,r)=1]E_{sq}F_{sr}sum_{k=1}^{lfloorfrac n{sqr}
floor}C_{sqrk}sum_{i=1}^{lfloorfrac n{sq}
floor}sum_{j=1}^{lfloorfrac n{sr}
floor}A_{isq}B_{jsr}D_{scdotgcd(iq,jr)}
end{align}]
设(C'_i=sum_{j=1}^{lfloorfrac ni
floor}C_{ij},A'_i=A_{si},B'_i=B_{si},D'_i=D_{si},m=lfloorfrac ns
floor)，则：
[egin{align}
&;;;;sum_{s=1}^nsum_{q=1}^{lfloorfrac ns
floor}sum_{r=1}^{lfloorfrac n{sq}
floor}[gcd(q,r)=1]E_{sq}F_{sr}sum_{k=1}^{lfloorfrac n{sqr}
floor}C_{sqrk}sum_{i=1}^{lfloorfrac n{sq}
floor}sum_{j=1}^{lfloorfrac n{sr}
floor}A_{isq}B_{jsr}D_{scdotgcd(iq,jr)}\
&=sum_{s=1}^nsum_{q=1}^{lfloorfrac ns
floor}sum_{r=1}^{lfloorfrac n{sq}
floor}[gcd(q,r)=1]E_{sq}F_{sr}C'_{sqr}sum_{i=1}^{lfloorfrac mq
floor}sum_{j=1}^{lfloorfrac mr
floor}A'_{iq}B'_{jr}D'_{gcd(iq,jr)}
end{align}]
将(D')反演，得
[egin{align}
&;;;;sum_{s=1}^nsum_{q=1}^{lfloorfrac ns
floor}sum_{r=1}^{lfloorfrac n{sq}
floor}[gcd(q,r)=1]E_{sq}F_{sr}C'_{sqr}sum_{i=1}^{lfloorfrac mq
floor}sum_{j=1}^{lfloorfrac mr
floor}A'_{iq}B'_{jr}sum_{p|iq,p|jr}D'_p\
&=sum_{s=1}^nsum_{q=1}^{lfloorfrac ns
floor}sum_{r=1}^{lfloorfrac n{sq}
floor}[gcd(q,r)=1]E_{sq}F_{sr}C'_{sqr}sum_{q|i}^mA'_isum_{p|i}D'_psum_{p|j}B'_j[j\%r=0]
end{align}]
借鉴之前的思路，枚举(s,q)，设(tmp_i=A'_i[i\%q=0])，对(tmp)进行变换(tmp'_i=D'_isum_{d|i}tmp_i)得(tmp')，再对(tmp')进行变换(tmp''_d=B'_dsum_{d|i}tmp'_i)得(tmp'')。
再枚举(r)，则(s,q,r)对答案的贡献为(E_{sq}F_{sr}C'_{sqr}sum_{i=1}^{lfloorfrac mr
floor}tmp''_{ir})
注意常数优化
代码太丑不贴了……