Minimizing the Sum of a Distinct Array with GCD k

Problem Description

Construct an array of n distinct positive integers whose greatest common divisor (GCD) equals k. Among all such arrays, the sum of the elements must be minimal. Output that minimal sum.

Input

Two positive integers n and k (1 ≤ n, k ≤ 10^5).

Output

A single integer: the minimal possible sum of the array.

Examples

Example 1

Input
3 1

Output
6

Explanation
The array [1, 2, 3] satisfies the conditions.

Example 2

Input
2 6

Output
18

Explanation
The array [6, 12] satisfies the conditions.

Solution Idea

The arithmetic progression [k, 2k, 3k, ..., nk] meets all requirements: the elements are distinct, their GCD is k, and the sum can be computed by the arithmetic series formula.

k + 2k + 3k + ... + nk = (1 + 2 + 3 + ... + n) * k = n*(n+1)/2 * k

Therefore the answer is (1 + n) * n * k // 2 Use a 64‑bit integer type (e.g., long in Java/C++) to avoid overflow.

Reference Implementations

Python

# Minimal sum array with GCD k
n, k = map(int, input().split())
print((1 + n) * n * k // 2)

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        long k = scanner.nextLong();
        System.out.println((1 + n) * n * k / 2);
        scanner.close();
    }
}

C++

#include <iostream>
using namespace std;
int main() {
    long n, k;
    cin >> n >> k;
    cout << (1 + n) * n * k / 2 << endl;
    return 0;
}

Complexity Analysis

Time complexity: O(1) Space complexity:

O(1)