小红的数组构造

[题目链接](https://www.nowcoder.com/practice/8844c80d55534f4e99bc0c1184a052e8)

思路

构造一个长度为 $n$ 的数组，要求所有元素互不相同，且 $\gcd$ 恰好等于 $g$ ，同时使元素之和最小。

关键观察

所有元素的 $\gcd = g$ ，意味着每个元素都必须是 $g$ 的倍数。设数组元素为 $a_1 g, a_2 g, \ldots, a_n g$ ，其中 $a_i$ 为互不相同的正整数，且 $\gcd(a_1, a_2, \ldots, a_n) = 1$ （否则公因子可以提出来， $\gcd$ 就会大于 $g$ ）。

要使总和 $g \cdot (a_1 + a_2 + \cdots + a_n)$ 最小，只需让 $a_1 + a_2 + \cdots + a_n$ 尽量小。

最优构造

取 $a_i = i$ （即 $1, 2, 3, \ldots, n$ ），此时：

元素互不相同。
$\gcd(1, 2, \ldots, n) = 1$ ，所以原数组的 $\gcd = g$ 。
和 $= g \cdot \frac{n(n+1)}{2}$ ，这已经是最小的 $n$ 个不同正整数之和，不可能更小。

样例验证

$n = 3, g = 1$ ：数组为 $\{1, 2, 3\}$ ，和 $= 1 \times 6 = 6$ 。
$n = 2, g = 2$ ：数组为 $\{2, 4\}$ ，和 $= 2 \times 3 = 6$ 。

代码

C++
Java
Python3
JavaScript

#include <iostream>
using namespace std;
int main() {
    long long n, g;
    cin >> n >> g;
    cout << g * n * (n + 1) / 2 << 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();
        System.out.println(g * n * (n + 1) / 2);
    }
}

n, g = map(int, input().split())
print(g * n * (n + 1) // 2)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
rl.on('line', (line) => {
    const [n, g] = line.trim().split(' ').map(BigInt);
    console.log((g * n * (n + 1n) / 2n).toString());
    rl.close();
});

复杂度分析

时间复杂度： $O(1)$ ，只需一次数学运算。
空间复杂度： $O(1)$ ，只使用常数个变量。