C++で2つの数の倍数を統合・ソートしたリストからN番目の値を求める方法

3つの整数 x、y、n が与えられたとき、x の倍数と y の倍数をすべて統合して昇順に並べたリストを作り、その中から n 番目の値を求める問題です。まずは具体例で確認してみましょう。

入力例

x = 2
y = 3
n = 7

出力例

10

考え方

2 の倍数(最初の7個)は「2, 4, 6, 8, 10, 12, 14」、3 の倍数(最初の7個)は「3, 6, 9, 12, 15, 18, 21」です。

これらを統合し、重複を除いて昇順にソートすると「2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 18, 21」となります。このリストの7番目の値は 10 です。

アルゴリズム

• 倍数を格納するための vector を用意する。
• x の最初の n 個の倍数を求め、vector に追加する。
• y の最初の n 個の倍数を順に調べる。
  • すでに vector に存在しない場合のみ追加する(重複を避けるため)。
• vector を昇順にソートする。
• n 番目の要素を返す。

C++での実装

上記のアルゴリズムをC++で実装したものが以下のコードです。

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

int findNthMultiple(int x, int y, int n) {
    vector<int> multiples;

    // x の最初の n 個の倍数を追加
    for (int i = 1; i <= n; i++) {
        multiples.push_back(x * i);
    }
    sort(multiples.begin(), multiples.end());

    // y の倍数を重複なく追加
    for (int i = 1; i <= n; i++) {
        if (!binary_search(multiples.begin(), multiples.end(), y * i)) {
            multiples.push_back(y * i);
            sort(multiples.begin(), multiples.end());
        }
    }

    return multiples[n - 1];
}

int main() {
    int x = 2, y = 3, n = 7;
    cout << findNthMultiple(x, y, n) << endl;
    return 0;
}

実行結果

このコードを実行すると、次の出力が得られます。

10

計算量のポイント

この実装では、y の倍数を追加するたびにソートを行っているため、最悪の場合 O(n² log n) の計算量になります。より効率化したい場合は、両者の倍数をすべて集めてから最後に一度だけソートする方法や、std::merge や std::set を活用する方法が有効です。