C++でAまたはBのいずれかで割り切れるN番目の項を求めるプログラム

この問題では、3つの整数 A、B、N が与えられます。求めるのは、「A または B のいずれかで割り切れる数」を小さい順に並べた数列の N 番目の項です。本記事では、C++ による2つの解法（線形探索と二分探索）を、サンプルコードとともにわかりやすく解説します。

問題の概要

A または B で割り切れる数を昇順に並べたとき、その N 番目の値を求めます。具体的には、1 から順に整数を調べ、「A で割り切れる」または「B で割り切れる」という条件を満たす数をカウントしていき、N 個目に到達した時点の数が答えとなります。

入力例

A = 4、B = 3、N = 5

出力例

9

解説

3 または 4 で割り切れる数を小さい順に並べると、次のようになります。

3, 4, 6, 8, 9, 12, …

この数列の 5 番目の項は 9 であるため、出力は 9 となります。

解法1：線形探索によるシンプルな実装

最も直感的な方法は、1 から順に各整数について「A または B で割り切れるか」を判定し、条件を満たす数をカウントしていく方法です。カウントが N に達したときの値が答えとなります。

実装例

#include<iostream>
using namespace std;

int findNTerm(int N, int A, int B) {
    int count = 0;
    int num = 1;
    while (count < N) {
        if (num % A == 0 || num % B == 0)
            count++;
        if (count == N)
            return num;
        num++;
    }
    return 0;
}

int main() {
    int N = 12, A = 3, B = 4;
    cout << N << "番目の項（" << A << " または " << B << " で割り切れる）は "
         << findNTerm(N, A, B) << endl;
}

実行結果

3 または 4 で割り切れる 12 番目の項は 24

この方法は実装が非常に簡単ですが、N や A・B の値が大きくなると処理時間が増加します。計算量はおよそ O(N × min(A, B)) です。

解法2：二分探索による効率的な実装

より高速に求めたい場合は、二分探索が有効です。「ある数 x 以下に存在する、A または B で割り切れる数の個数」は、包除原理を用いて次の式で求められます。

count(x) = x / A + x / B − x / LCM(A, B)

ここで LCM(A, B) は A と B の最小公倍数です。x / LCM(A, B) を引くのは、A と B の両方で割り切れる数（＝最小公倍数の倍数）が二重にカウントされるのを防ぐためです。

この個数関数は単調増加するため、「count(x) ≥ N となる最小の x」を二分探索で求めれば、それがまさに N 番目の項となります。

実装例

#include <iostream>
using namespace std;

// 最小公倍数（LCM）を求める関数
int findLCM(int a, int b) {
    int LCM = a, i = 2;
    while (LCM % b != 0) {
        LCM = a * i;
        i++;
    }
    return LCM;
}

int findNTerm(int N, int A, int B) {
    int start = 1, end = (N * A * B), mid;
    int LCM = findLCM(A, B);

    while (start < end) {
        mid = start + (end - start) / 2;
        if (((mid / A) + (mid / B) - (mid / LCM)) < N)
            start = mid + 1;
        else
            end = mid;
    }
    return start;
}

int main() {
    int N = 12, A = 3, B = 4;
    cout << N << "番目の項（" << A << " または " << B << " で割り切れる）は "
         << findNTerm(N, A, B);
}

実行結果

3 または 4 で割り切れる 12 番目の項は 24

探索範囲の上限は N × A × B としています。これは「N 番目の項が必ずこの範囲内に収まる」ことを保証する、十分に大きな値です。二分探索部分の計算量は O(log(N × A × B)) となり、線形探索よりも大幅に高速に動作します。

まとめ

A または B で割り切れる N 番目の項を求める問題に対して、
・1 から順に数え上げる線形探索（実装が簡単・計算量 O(N × min(A, B))）
・包除原理と最小公倍数を組み合わせた二分探索（高速・計算量 O(log(N × A × B))）
の2つのアプローチを紹介しました。小規模な入力であれば前者、大きな N を扱う場合は後者を選ぶとよいでしょう。