题面
题解
设 (mathbf f' = mathbf f * mu)，(G_{mathbf f} (n) = sum_{n | d} mathbf f(d))，记 ((i, j) = gcd(i, j))，([i, j] = operatorname{lcm}(i, j))。
令 (S_i=A_{id}, T_i = B_{id}, W_i = D_{id}, m = leftlfloor frac nd ight floor)。
于是：
[egin{aligned}
&sum_{i=1}^nsum_{j=1}^nsum_{k=1}^n A_iB_jC_kD_{(i, j)}E_{(i, k)}F_{(j, k)}\
=&sum_{k=1}^n C_ksum_{i=1}^nsum_{j=1}^n A_iB_jD_{(i, j)}sum_{p|i,p|k} E'_p sum_{q|j,q|k} F'_q\
=&sum_{[p, q] leq n} E'_{p} F'_qG_c([p, q]) sum_{pi leq n} A_{pi}sum_{qj leq n} B_{qj} D_{(pi,qj)}\
=&sum_{d=1}^nsum_{xyleq lfloor frac nd
floor, (x,y) = 1} E'_{dx}F'_{dy}G_c(dxy)sum_{ixleq lfloor frac nd
floor} A_{ixd} sum_{jy leq lfloor frac nd
floor} B_{jyd} D_{d(ix,jy)}\
=&sum_{d=1}^nsum_{xyleq lfloor frac nd
floor, (x,y) = 1} E'_{dx}F'_{dy}G_c(dxy)sum_{ix leq m} S_{ix} sum_{jy leq m} T_{yj} sum_{r|ix, r|jy} W'_r\
=&sum_{d=1}^nsum_{xyleq lfloor frac nd
floor, (x,y) = 1} E'_{dx}F'_{dy}G_c(dxy)sum_{ix leq m} S_{ix} sum_{r|ix} W'_r sum_{r|jy} T_{jy}\
=&sum_{d=1}^nsum_{xyleq lfloor frac nd
floor, (x,y) = 1} E'_{dx}F'_{dy}G_c(dxy)sum_{x | u} S_u sum_{r | u} W'_r sum_{r | v} [y | v] T_v
end{aligned}
]
令 (x leq y)（(x > y) 同理），先暴力枚举 (d)，处理出 (S, T) 和 (W)，然后枚举 (x)，那么后面三个 (sum) 相当于三次卷积，然后枚举和 (x) 互质的 (y) 即可，卷积可以用魔力筛优化到 (mathcal O(n log log n))。
由于 (x leq sqrt n)，所以时间复杂度为 (mathcal O(sum_{d=1}^n leftlfloor frac nd ight floor^{frac 32} log log leftlfloor frac nd ight floor) = mathcal O(n sqrt n log log n))。
但是旧试题我卡不过去 /kk
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
const int N(1e5 + 10);
using ull = unsigned long long;
int n, prime[N], not_prime[N], cnt;
ull a[N], b[N], c[N], d[N], e[N], f[N], s[N], t[N], w[N], p[N], ans;
void F(ull *f, int N) { for (int j = 1; j <= cnt && prime[j] <= N; j++) for (int i = N / prime[j]; i; i--) f[i * prime[j]] -= f[i]; }
void G(ull *f, int N) { for (int j = 1; j <= cnt && prime[j] <= N; j++) for (int i = N / prime[j]; i; i--) f[i] += f[i * prime[j]]; }
void H(ull *f, int N) { for (int j = 1; j <= cnt && prime[j] <= N; j++) for (int i = 1; i * prime[j] <= N; i++) f[i * prime[j]] += f[i]; }
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%llu", a + i);
for (int i = 1; i <= n; i++) scanf("%llu", b + i);
for (int i = 1; i <= n; i++) scanf("%llu", c + i);
for (int i = 1; i <= n; i++) scanf("%llu", d + i);
for (int i = 1; i <= n; i++) scanf("%llu", e + i);
for (int i = 1; i <= n; i++) scanf("%llu", f + i);
for (int i = 2; i <= n; i++)
{
if (!not_prime[i]) prime[++cnt] = i;
for (int j = 1; j <= cnt && i * prime[j] <= n; j++)
{ not_prime[i * prime[j]] = 1; if (!(i % prime[j])) continue; }
}
F(e, n), F(f, n), G(c, n);
for (int i = 1, m; i <= n; i++)
{
m = n / i;
for (int j = 1; j <= m; j++) p[j] = a[j * i], t[j] = b[j * i], w[j] = d[j * i]; F(w, m);
for (int x = 1; x * x <= m; x++)
{
std::memset(s, 0, (m + 1) << 3);
for (int j = x; j <= m; j += x) s[j] = p[j]; G(s, m);
for (int j = 1; j <= m; j++) s[j] *= w[j]; H(s, m);
for (int j = 1; j <= m; j++) s[j] *= t[j]; G(s, m);
for (int y = x; x * y <= m; y++) if (std::__gcd(x, y) == 1)
ans += e[x * i] * f[y * i] * c[x * y * i] * s[y];
std::memset(s, 0, (m + 1) << 3);
for (int j = x; j <= m; j += x) s[j] = t[j]; G(s, m);
for (int j = 1; j <= m; j++) s[j] *= w[j]; H(s, m);
for (int j = 1; j <= m; j++) s[j] *= p[j]; G(s, m);
for (int y = x + 1; x * y <= m; y++) if (std::__gcd(x, y) == 1)
ans += e[y * i] * f[x * i] * c[x * y * i] * s[y];
}
}
printf("%llu
", ans);
return 0;
}