题目分析

题意理解

我们需要计算：

$$\sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n A_i B_j C_k D_{\gcd(i,j)} E_{\gcd(i,k)} F_{\gcd(j,k)} $$

这是一个三重循环的gcd卷积问题，直接计算复杂度为 O(n³)，无法通过。

关键难点

1. 三重gcd约束：三个下标通过gcd相互关联
2. 大范围数据：n ≤ 10⁵，需要高效算法
3. 模2⁶⁴：使用unsigned long long自然溢出

算法思路

核心思想：莫比乌斯反演 + 狄利克雷卷积

1. 问题转化

利用莫比乌斯反演将gcd条件分解：

$$\gcd(i,j)=d \iff d|i, d|j \text{ 且 } \gcd(\frac{i}{d},\frac{j}{d})=1 $$

2. 重写求和式

原式可重写为：

$$\sum_{d_1,d_2,d_3} D_{d_1} E_{d_2} F_{d_3} \sum_{\substack{i,j,k \\ d_1|i,d_1|j \\ d_2|i,d_2|k \\ d_3|j,d_3|k}} A_i B_j C_k [\gcd(\frac{i}{d_1},\frac{j}{d_1})=1] [\gcd(\frac{i}{d_2},\frac{k}{d_2})=1] [\gcd(\frac{j}{d_3},\frac{k}{d_3})=1] $$

3. 使用莫比乌斯函数

利用性质：$[gcd(a,b)=1] = \sum_{d|gcd(a,b)} \mu(d)$

通过多次反演，将条件分解为独立的求和。

代码详解

#include <bits/stdc++.h>
using namespace std;

namespace Main {
#define int unsigned long long  // 自动模2^64

const int N = 1e5 + 10, Blk = 320;

int n;
int ans;

vector<int> prime;
bool nprime[N];
int My_GCD[Blk + 5][Blk + 5];  // 预计算小范围gcd

// 线性筛预处理质数
void Maths_Prew() {
    rep(i, 2, n) {
        if (!nprime[i]) prime.emplace_back(i);
        for (const int &g : prime) {
            if (i * g > n) break;
            nprime[i * g] = 1;
            if (i % g == 0) break;
        }
    }
    
    // 预计算小范围gcd
    rep(i, 0, Blk) rep(j, 0, Blk)
        My_GCD[i][j] = __gcd(i, j);
}

// 优化gcd计算
int calc_gcd(int x, int y) {
    if (x > y) swap(x, y);
    assert(x <= Blk);
    return My_GCD[x][y % x];  // 利用预计算表
}

// 莫比乌斯变换：arr[i] = sum_{d|i} μ(i/d) * arr[d]
void Mbius(int len, int arr[]) {
    for (const int &g : prime) {
        if (g > len) break;
        // 从大到小处理，避免重复计算
        per(i, len / g, 1)
            arr[i * g] -= arr[i];
    }
}

// 狄利克雷前缀和：arr[i] = sum_{d|i} arr[d]
void Dirichlet_Prefix(int len, int arr[]) {
    for (const int &g : prime) {
        if (g > len) break;
        rep(i, 1, len / g)
            arr[i * g] += arr[i];
    }
}

// 狄利克雷后缀和：arr[i] = sum_{i|d} arr[d]  
void Dirichlet_Suffix(int len, int arr[]) {
    for (const int &g : prime) {
        if (g > len) break;
        per(i, len / g, 1)
            arr[i] += arr[i * g];
    }
}

// 临时数组
int A[N], B[N], C[N], D[N], E[N], F[N], G1[N];
int a[N], b[N], c[N], d[N], e[N], f[N], G2[N];

// 序列变换：narr[i] = oarr[i * step]
void trans(int len, int oarr[], int narr[], int step) {
    for (int i = 1, j = step; j <= len; ++i, j += step)
        narr[i] = oarr[j];
}

// 主求解函数
void Solve(int T) {
    int m = n / T;  // 缩放后的范围
    
    // 对d进行莫比乌斯变换
    Mbius(m, d);
    // 对c进行狄利克雷后缀和
    Dirichlet_Suffix(m, c);

    // 枚举p，优化复杂度
    for (int p = 1; p * p <= m; ++p) {
        fill(G1, G1 + m + 1, 0);
        fill(G2, G2 + m + 1, 0);

        // 筛选p的倍数
        for (int i = p; i <= m; i += p) {
            G1[i] = a[i];  // A序列
            G2[i] = b[i];  // B序列
        }

        // 狄利克雷后缀和
        Dirichlet_Suffix(m, G1);
        Dirichlet_Suffix(m, G2);

        // 乘以d并做前缀和
        rep(i, 1, m) {
            G1[i] *= d[i];
            G2[i] *= d[i];
        }
        Dirichlet_Prefix(m, G1);
        Dirichlet_Prefix(m, G2);

        // 乘以对应的序列值
        rep(i, 1, m) {
            G1[i] *= b[i];  // G1[i]用于(p,q)情况
            G2[i] *= a[i];  // G2[i]用于(q,p)情况
        }

        // 枚举q，满足p*q <= m
        for (int q = p; q * p <= m; ++q) {
            // 检查gcd(p,q)=1
            if (calc_gcd(p, q) > 1) continue;

            // 计算贡献
            for (int i = q; i <= m; i += q) {
                // (p,q)情况的贡献
                ans += e[p] * f[q] * c[p * q] * G1[i];
                
                // 如果p≠q，计算对称情况(q,p)
                if (p != q)
                    ans += e[q] * f[p] * c[q * p] * G2[i];
            }
        }
    }
}

void ERoRain() {
    n = read();
    Maths_Prew();

    // 读入六个序列
    rep(i, 1, n) A[i] = read();
    rep(i, 1, n) B[i] = read();
    rep(i, 1, n) C[i] = read();
    rep(i, 1, n) D[i] = read();
    rep(i, 1, n) E[i] = read();
    rep(i, 1, n) F[i] = read();

    // 对E,F进行莫比乌斯变换
    Mbius(n, E);
    Mbius(n, F);

    // 枚举T，分解问题
    rep(i, 1, n) {
        // 对每个T，重新缩放序列
        trans(n, A, a, i);
        trans(n, B, b, i);
        trans(n, C, c, i);
        trans(n, D, d, i);
        trans(n, E, e, i);
        trans(n, F, f, i);
        
        Solve(i);
    }

    write(ans);
    puts("");
}

signed main() {
    int T = 1;
    while (T--) ERoRain();
    return 0;
}

} signed main() {
    Main::main();
    return 0;
}

算法核心要点详解

1. 莫比乌斯反演的应用

代码中多次使用莫比乌斯变换来分解gcd条件：

void Mbius(int len, int arr[]) {
    for (const int &g : prime) {
        if (g > len) break;
        per(i, len / g, 1)
            arr[i * g] -= arr[i];
    }
}

这实际上计算的是：$arr[i] = \sum_{d|i} \mu(\frac{i}{d}) \cdot arr[d]$

2. 狄利克雷卷积优化

通过狄利克雷前缀/后缀和，将复杂度从O(n²)降低到O(n log n)：

• 前缀和：$f(i) = \sum_{d|i} g(d)$
• 后缀和：$f(i) = \sum_{i|d} g(d)$

3. 问题分解策略

将原三重求和分解为：

1. 外层循环：枚举缩放因子 T
2. 中层循环：枚举质数因子 p, q
3. 内层循环：利用预计算结果快速求和

4. 复杂度分析

• 预处理：O(n log log n)
• 主算法：O(n log² n)
• 总复杂度：能够处理 n=10⁵ 的数据

关键优化技巧

1. 预计算小范围gcd

int calc_gcd(int x, int y) {
    if (x > y) swap(x, y);
    assert(x <= Blk);
    return My_GCD[x][y % x];
}

对于小范围的gcd，使用预计算表加速。

2. 质数分解优化

只枚举质数进行变换，避免重复计算。

3. 对称性利用

当p≠q时，(p,q)和(q,p)是对称的，可以一起计算。

总结

这道题综合运用了：

1. 莫比乌斯反演 分解gcd条件
2. 狄利克雷卷积 优化求和
3. 数论分块 降低复杂度
4. 质数筛法 预处理
5. 对称性优化 减少计算量

是一个很好的数论与组合数学综合题目，考察了莫比乌斯反演和狄利克雷卷积的深入应用。