C++で2つの等差数列の最初の衝突点（共通項）を求める方法

この記事では、2つの等差数列に共通して現れる最初の値――いわゆる「衝突点（コリジョンポイント）」――を見つけるC++プログラムについて解説します。

問題の概要

まず、5つの変数「a」「b」「c」「d」「n」が与えられます。これらの変数をもとに、それぞれn項からなる次の2つの等差数列（算術級数）を作成します。

b, b+a, b+2a, …, b+(n−1)a
d, d+c, d+2c, …, d+(n−1)c

そのうえで、この2つの数列の両方に共通して含まれる最初の値を求めることが目的です。

解法のアプローチ

この問題は、次の手順で解くことができます。

1. 第1の数列の項を先頭から順に1つずつ生成します。
2. 生成した各項 x に対して、次の2つの条件をチェックします。
   • x が第2の数列の初項「d」以上であること
   • x と「d」の差（x − d）が公差「c」で割り切れること
3. 両方の条件を満たした場合、その時点の値 x が最初の衝突点となります。

「x − d ≥ 0」という条件は、x が第2の数列の範囲内に存在しうることを保証するために必要です。また、「(x − d) % c == 0」は、x が第2の数列の項として表現できるかどうかを判定する条件です。

サンプルコード

#include<bits/stdc++.h>
using namespace std;
void calc_series(int a, int b, int c, int d, int n) {
    int x , flag = 0;
    // 第1の数列の項を生成
    for (int i = 0; i < n; i++) {
        x = b + i * a;
        // 第2の数列に存在するかどうかを確認
        if ((x - d) % c == 0 and x - d >= 0){
            cout << "First collision point : "<< x << endl;
            flag = 1;
            break;
        }
    }
    if(flag == 0) {
        cout << "No collision point exists" << endl;
    }
}
int main() {
    int a = 16;
    int b = 9;
    int c = 23;
    int d = 19;
    int n = 78;
    calc_series(a, b, c, d, n);
    return 0;
}

実行結果

First collision point : 249

コードの解説

calc_series 関数では、for ループを使って第1の数列の各項 x = b + i * a を順番に計算しています。各項について、「(x − d) % c == 0 かつ x − d ≥ 0」という条件式で第2の数列との一致を判定し、条件を満たした時点でその値を出力して break 文によりループを抜けます。

フラグ変数 flag は、衝突点が見つかったかどうかを記録するために使われています。ループが完了しても flag が 0 のままであれば、共通項が存在しないことを意味するため、「No collision point exists（衝突点は存在しない）」というメッセージが出力されます。

上記の例では、a=16、b=9、c=23、d=19、n=78 という入力に対して、最初の衝突点として 249 が出力されています。