思路分析

1. 分数公式化简

首先，我们分析分数的计算公式。分数由两部分组成：

• 正贡献项: 序列中所有下标是 $x$ 的倍数的元素之和, 即 $\sum a_{i \cdot x}$。
• 负贡献项: 序列中所有下标是 $y$ 的倍数的元素之和, 即 $\sum a_{j \cdot y}$。

我们考虑一个下标 $k$，如果它同时是 $x$ 的倍数和 $y$ 的倍数，那么它一定是 $x$ 和 $y$ 的最小公倍数 $\text{lcm}(x, y)$ 的倍数。在这种情况下，元素 $a_k$ 会在正贡献项中被加一次，在负贡献项中被减一次，所以 $a_k - a_k = 0$，它们对总分数的贡献相互抵消了。

因此，真正影响最终分数的只有那些仅是其中一个数的倍数的下标对应的元素：

• 纯正贡献: 下标是 $x$ 的倍数但不是 $y$ 的倍数。
• 纯负贡献: 下标是 $y$ 的倍数但不是 $x$ 的倍数。

这样，分数公式可以被化简为： $\text{Score}$ = ($\text{在纯正贡献位置的元素之和}$) - ($\text{在纯负贡献位置的元素之和}$)$

2. 最大化策略

为了让这个分数最大，我们应该：

1. 将序列中 最大 的一批数放到“纯正贡献”的位置上，来最大化被加上的部分。
2. 将序列中 最小 的一批数放到“纯负贡献”的位置上，来最小化被减去的部分。

因为序列元素可以任意交换，所以我们可以自由地将任何数值分配到任何位置。

3. 计算位置数量

接下来，我们需要确定这两种位置分别有多少个。

• 纯正贡献位置数量 ($count_{pos}$):

  • 所有 $x$ 的倍数位置的数量为 $\lfloor n/x \rfloor$。
  • 所有 $x, y$ 公倍数位置的数量为 $\lfloor n/\text{lcm}(x, y) \rfloor$。
  • 所以，纯正贡献位置的数量为：$count_{pos}$= $\lfloor n/x \rfloor$ - $\lfloor n/\text{lcm}(x, y) \rfloor$。

• 纯负贡献位置数量 ($count_{neg}$):

  • 同理，纯负贡献位置的数量为：$count_{neg}$= $\lfloor n/y \rfloor$ - $\lfloor n/\text{lcm}(x, y) \rfloor$。

这里需要用到最小公倍数 $\text{lcm}(x, y)$ 和最大公约数 $\text{gcd}(x, y)$ 的关系：$\text{lcm}(x, y)$ = $(x \cdot y)$ / $\text{gcd}(x, y)$。

4. 高效计算

如果对每次查询都进行排序和查找，效率会很低。我们可以通过预处理来优化。

1. 排序: 首先，将整个序列 $a$ 从小到大排序。

2. 前缀和: 然后，计算排序后序列的前缀和数组 $ps$。$ps[k]$ 存储排序后前 $k$ 个元素的和。使用64位整型（long long 或 long）来避免溢出。

3. 查询: 对于每一组查询 $(x, y)$：

   • 计算出 $count_{pos}$ 和 $count_{neg}$。
   • 需要加上的和，是序列中 $count_{pos}$ 个最大元素的和。在排好序的数组中，这等价于 ps[n] - ps[n - count_pos]。
   • 需要减去的和，是序列中 $count_{neg}$ 个最小元素的和。这等价于 ps[count_neg]。
   • 最终的最大分数为：$(ps[n] - ps[n - count_{pos}]) - ps[count_{neg}]$。

这个方法的总时间复杂度为 $O(N \log N + Q \log N)$，其中 $N \log N$ 用于排序，$Q \log N$ 用于处理 $Q$ 次查询（每次查询的瓶颈是计算 gcd）。这对于给定的数据范围是足够高效的。

C++

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// 计算最大公约数 (Greatest Common Divisor)
long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 计算最小公倍数 (Least Common Multiple)
long long lcm(long long a, long long b) {
    if (a == 0 || b == 0) return 0;
    // (a / gcd(a, b)) * b 可以避免 a*b 溢出
    return (a / gcd(a, b)) * b;
}

int main() {
    // 快速输入输出
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, q;
    std::cin >> n >> q;

    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 将序列从小到大排序
    std::sort(a.begin(), a.end());

    // 计算前缀和数组，ps[i] 表示前 i 个元素的和
    // 使用 long long 防止溢出
    std::vector<long long> ps(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        ps[i + 1] = ps[i] + a[i];
    }

    // 处理 q 次查询
    for (int k = 0; k < q; ++k) {
        int x, y;
        std::cin >> x >> y;

        // 计算lcm
        long long l = lcm(x, y);

        // 计算纯正贡献和纯负贡献位置的数量
        // 如果 l > n, n/l 会是 0
        long long common_multiples = (l > n) ? 0 : (n / l);
        long long count_pos = n / x - common_multiples;
        long long count_neg = n / y - common_multiples;

        // 计算最大分数
        // sum_largest_pos: count_pos 个最大元素的和
        // sum_smallest_neg: count_neg 个最小元素的和
        long long sum_largest_pos = ps[n] - ps[n - count_pos];
        long long sum_smallest_neg = ps[count_neg];

        std::cout << sum_largest_pos - sum_smallest_neg << "\n";
    }

    return 0;
}

Python

import sys
import math

# 使用 python 自带的 gcd 函数
def gcd(a, b):
    return math.gcd(a, b)

# 计算最小公倍数
def lcm(a, b):
    if a == 0 or b == 0:
        return 0
    # python 的整数类型可以自动处理大数，不会溢出
    return (a * b) // gcd(a, b)

def solve():
    # 快速输入
    input = sys.stdin.readline
    n, q = map(int, input().split())
    a = list(map(int, input().split()))

    # 将序列从小到大排序
    a.sort()

    # 计算前缀和数组
    ps = [0] * (n + 1)
    for i in range(n):
        ps[i + 1] = ps[i] + a[i]

    # 处理 q 次查询
    for _ in range(q):
        x, y = map(int, input().split())

        # 计算 lcm
        l = lcm(x, y)

        # 计算纯正贡献和纯负贡献位置的数量
        # 如果 l > n, n // l 会是 0
        common_multiples = n // l if l <= n else 0
        count_pos = n // x - common_multiples
        count_neg = n // y - common_multiples

        # 计算最大分数
        # sum_largest_pos: count_pos 个最大元素的和
        # sum_smallest_neg: count_neg 个最小元素的和
        sum_largest_pos = ps[n] - ps[n - count_pos]
        sum_smallest_neg = ps[count_neg]

        print(sum_largest_pos - sum_smallest_neg)

solve()

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Main {

    // 计算最大公约数
    private static long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    // 计算最小公倍数
    private static long lcm(long a, long b) {
        if (a == 0 || b == 0) return 0;
        // (a / gcd(a, b)) * b 可以避免 a*b 溢出
        return (a / gcd(a, b)) * b;
    }

    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 进行快速输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());

        int[] a = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }

        // 将序列从小到大排序
        Arrays.sort(a);

        // 计算前缀和数组，ps[i] 表示前 i 个元素的和
        // 使用 long 防止溢出
        long[] ps = new long[n + 1];
        ps[0] = 0;
        for (int i = 0; i < n; i++) {
            ps[i + 1] = ps[i] + a[i];
        }

        StringBuilder sb = new StringBuilder();
        // 处理 q 次查询
        for (int k = 0; k < q; k++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            // 计算lcm
            long l = lcm(x, y);

            // 计算纯正贡献和纯负贡献位置的数量
            // 如果 l > n, n/l 会是 0
            long commonMultiples = (l > n) ? 0 : (n / l);
            long countPos = n / x - commonMultiples;
            long countNeg = n / y - commonMultiples;

            // 计算最大分数
            // sumLargestPos: countPos 个最大元素的和
            // sumSmallestNeg: countNeg 个最小元素的和
            long sumLargestPos = ps[n] - ps[n - (int)countPos];
            long sumSmallestNeg = ps[(int)countNeg];

            sb.append(sumLargestPos - sumSmallestNeg).append("\n");
        }
        System.out.print(sb.toString());
    }
}

题目内容

多多有一个长度为 $n$ 的序列 $(a_1,a_2,...,a_n)$，对于给定的 $x$ 和 $y$ ；

一个序列的分数定义为 $\sum_{1}^{\left\lfloor\frac{n}{x}\right\rfloor} a_{i \cdot x}-\sum_{1}^{\left\lfloor\frac{n}{y}\right\rfloor} a_{j \cdot y}$

序列元素可任意交换位置，得到一个新的序列。多多想知道，经过若干次操作后，新的序列的最大分数是多少。

输入描述

第一行为 $2$ 个数字，$n,q$ ，其中 $n≤2*10^5,q≤10^4$

接下来 $1$ 行 $n$ 个数字，分别为 $a_1,a_2,...,a_n$ ，其中 $0≤a_1＜10^9$

接下来 $q$ 行，每行两个数字 $x,y$ ，其中 $1≤x,y≤n$

输出描述

输出 $q$ 行，每行包含一个数字，代表序列的最大分数

样例1

输入

7 1
5 9 3 8 2 10 3
2 3

输出

17

说明

按照题目中的分数定义，序列的分数为

$(a_2+a_4+a_6)-(a_3+a_6)$ ；

经过元素交换后一种可能的序列为

$3$ $9$ $2$ $10$ $8$ $5$ $3$ ，

此时分数最大为 $(9+10+5)-(2+5)=17$