解题思路

• 将下标按相同的值 ⌊n/i⌋ 分组。对每个分组内的任意两元素，我们可以把它们同时变成它们的 gcd，该操作可无限次执行。
• 关键性质：在同一分组内，经过若干次操作，可以把该分组的所有元素都变成该分组所有元素的整体最大公约数 G（因为两两替换为 gcd 可逐步把所有数“收缩”到整体 gcd）。这样该分组的元素和变为 组大小 × G，且这是最小值。
• 因而答案为：对所有分组求其元素 gcd 并乘以分组大小后累加。
• 实现要点：⌊n/i⌋ 的取值个数是 O(√n)。可用分块：令 l=1，令 q=n//l，则区间 [l, r]（其中 r=n//q）的下标满足同一 ⌊n/i⌋。遍历这些区间即可。

复杂度分析

• 对每个测试用例，仅遍历每个分块一次并计算区间 gcd： 时间复杂度 O(√n + n)（等价于线性扫一遍并在分块边界统计），整体在约 O(n)。
• 额外空间复杂度 O(1)（只需若干临时变量）。

代码实现

Python

# 题意函数：给定 n 与数组 a，返回最小可能的数组元素和
from math import gcd
import sys

def min_sum_after_ops(n, a):
    ans = 0
    l = 1
    # 分块：相同 floor(n/i) 的下标连续
    while l <= n:
        q = n // l
        r = n // q
        g = 0
        # 计算该组的整体 gcd
        for i in range(l - 1, r):  # a 为 0-based
            g = a[i] if g == 0 else gcd(g, a[i])
        ans += (r - l + 1) * g
        l = r + 1
    return ans

def main():
    data = list(map(int, sys.stdin.read().strip().split()))
    t = data[0]
    idx = 1
    out = []
    for _ in range(t):
        n = data[idx]; idx += 1
        a = data[idx:idx+n]; idx += n
        out.append(str(min_sum_after_ops(n, a)))
    print("\n".join(out))

if __name__ == "__main__":
    main()

Java

// ACM 风格：主类 Main，读入 T 组数据，逐组输出答案
import java.io.*;
import java.util.*;

public class Main {

    // 题意函数：给定 n 和数组 a，返回最小可能的数组元素和
    static long minSumAfterOps(int n, int[] a) {
        long ans = 0L;
        int l = 1;
        while (l <= n) {
            int q = n / l;
            int r = n / q;
            int g = 0;
            // 计算该组整体 gcd
            for (int i = l - 1; i <= r - 1; i++) {
                g = (g == 0) ? a[i] : gcd(g, a[i]);
            }
            ans += (long)(r - l + 1) * g;
            l = r + 1;
        }
        return ans;
    }

    // 辗转相除法
    static int gcd(int x, int y) {
        while (y != 0) {
            int t = x % y;
            x = y;
            y = t;
        }
        return x;
    }

    // 由于数据量较大，使用快速输入
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do { c = read(); } while (c <= ' ');
            if (c == '-') { sgn = -1; c = read(); }
            while (c > ' ') {
                x = x * 10 + (c - '0');
                c = read();
            }
            return x * sgn;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        StringBuilder sb = new StringBuilder();
        int T = fs.nextInt();
        while (T-- > 0) {
            int n = fs.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = fs.nextInt();
            sb.append(minSumAfterOps(n, a)).append('\n');
        }
        System.out.print(sb.toString());
    }
}

C++

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

// 自写 gcd，兼容老标准
static inline int mygcd(int a, int b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    while (b) { int t = a % b; a = b; b = t; }
    return a;
}

long long min_sum_after_ops(int n, const vector<int>& a) {
    long long ans = 0;
    int l = 1;
    while (l <= n) {
        int q = n / l;
        int r = n / q;           // 同一组的右端点
        int g = 0;
        for (int i = l - 1; i <= r - 1; ++i) {
            g = (g == 0) ? a[i] : mygcd(g, a[i]); // 用自写 gcd
        }
        ans += 1LL * (r - l + 1) * g;
        l = r + 1;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        cout << min_sum_after_ops(n, a) << "\n";
    }
    return 0;
}

题目内容

给定一个长度为$n$ 的数组{$a_1,a_2,...,a_n$} 。 你可以对数组执行以下操作任意次：

• 选择两个不同的下标$i,j$ ，满足$1≤i≤j$ 且[$n/i$]=[$n/j$] ；
• 将$a_i$ 与$a_j$ 同时替换为$gcd(a_i,a_j)$ 。 请输出操作后（或者不执行任何操作）数组所有元素之和的最小值。

【名词解释】

• $[x]$：代表对 $x$进行下取整操作，得到不超过 $x$的最大整数。
• 最大公约数（$gcd$）：指两个或多个整数共有约数中最大的一个。例如，$12$ 和 $30$ 的公约数有$1, 2, 3, 6$，其中最大的约数是$6$，因此记作$gcd(12,30)=6$ 。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T(1≤T≤10^4)$代表数据组数，每组测试数据描述如下：

• 第一行输入一个整数$n(1≤n≤2×10^5)代$表数组长度；
• 第二行输入$n$个整数 $a_1,a_2,...,a_n(1≤a_i≤10^9)$代表数组中的元素； 除此之外，保证单个测试文件的$n$之和不超过$2×10^5$ 。

输出描述

对于每一组测试数据，新起一行输出一个整数，表示操作后数组所有元素之和的最小值。

样例1

输入

1 
6
1 2 3 7 8 9

输出

9