题解 | #小红的数组构造#

题目链接

小红的数组构造

题目描述

小红希望构造一个数组，满足以下三个条件：

数组共有 $n$ 个元素，且所有元素两两不相等。
所有元素的最大公约数（GCD）等于 $g$ 。
所有元素之和尽可能小。

你需要输出这个数组元素之和的最小值。

解题思路

这是一个基于数论性质的构造题。我们的目标是找到一个满足条件的数组，使其元素之和最小。

1. 分析 GCD 条件

设我们要构造的数组为 $A = \{a_1, a_2, \ldots, a_n\}$ 。

根据题目条件， $\gcd(a_1, a_2, \ldots, a_n) = g$ 。

由最大公约数的定义可知，数组中的每一个元素 $a_i$ 都必须是 $g$ 的倍数。因此，我们可以将每个元素表示为 $a_i = g \cdot b_i$ 的形式，其中 $b_i$ 是一个正整数。

将这个关系代入 GCD 条件中：

$\gcd(g \cdot b_1, g \cdot b_2, \ldots, g \cdot b_n) = g$

根据 GCD 的分配律性质，我们可以提出公因子 $g$ ：

$g \cdot \gcd(b_1, b_2, \ldots, b_n) = g$

由此可以推断出，系数数组 $B = \{b_1, b_2, \ldots, b_n\}$ 必须满足：

$\gcd(b_1, b_2, \ldots, b_n) = 1$

同时，因为原数组 $A$ 的所有元素 $a_i$ 必须两两不相等，所以系数数组 $B$ 的所有元素 $b_i$ 也必须两两不相等。

2. 分析最小和条件

我们需要最小化数组 $A$ 的元素之和 $S$ ：

$S = \sum_{i=1}^{n} a_i = \sum_{i=1}^{n} (g \cdot b_i) = g \cdot \left(\sum_{i=1}^{n} b_i\right)$

由于 $g$ 是一个给定的正整数，要最小化总和 $S$ ，我们必须最小化系数数组 $B$ 的元素之和 $\sum b_i$ 。

3. 综合求解

现在问题转化为：寻找 $n$ 个两两不相等的正整数 $b_i$ ，使得它们的 GCD 为 1，并且它们的和最小。

为了使和最小，我们应该选择尽可能小的正整数。最自然的选择是最小的 $n$ 个正整数，即集合 $\{1, 2, 3, \ldots, n\}$ 。

我们来验证这个选择是否满足条件：

两两不相等：满足。
GCD 为 1：因为集合中包含了元素 1，所以 $\gcd(1, 2, 3, \ldots, n) = 1$ 。满足。

这个集合不仅满足所有条件，而且其元素之和是所有满足“ $n$ 个不同正整数”这一条件的集合中最小的。因此，这是我们的最优选择。

4. 计算最终答案

我们已经确定了最优的系数数组 $B$ 为 $\{1, 2, 3, \ldots, n\}$ 。因此，最优的原数组 $A$ 为 $\{g \cdot 1, g \cdot 2, \ldots, g \cdot n\}$ 。

其最小和为：

$S_{min} = g \cdot (1 + 2 + 3 + \ldots + n)$

利用等差数列求和公式 $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ ，我们得到最终的答案：

$S_{min} = g \cdot \frac{n(n+1)}{2}$

代码

cpp
java
python

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n, g;
    cin >> n >> g;

    long long sum_of_b = n * (n + 1) / 2;
    long long min_sum = g * sum_of_b;

    cout << min_sum << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long g = sc.nextLong();

        long sumOfB = n * (n + 1) / 2;
        long minSum = g * sumOfB;

        System.out.println(minSum);
    }
}

import sys

def solve():
    try:
        line = sys.stdin.readline().strip()
        if not line:
            return
        n, g = map(int, line.split())
        
        sum_of_b = n * (n + 1) // 2
        min_sum = g * sum_of_b
        
        print(min_sum)
        
    except (IOError, ValueError):
        return

solve()

算法及复杂度

算法：数学推导
时间复杂度： $O(1)$ 。
- 我们通过数学推导得出了一个直接计算的公式，所以只需要进行几次乘法和除法运算，时间复杂度是常数级别的。
空间复杂度： $O(1)$ 。
- 程序只需要存储几个变量，不需要额外的空间。