C++で指定した数が無限の等差数列に存在するかどうかを判定する方法

3つの整数 a、b、c が与えられたとします。初項を a、公差を c とする無限に続く等差数列を考えたとき、b がこの数列に含まれるかどうかを判定するのが本記事のテーマです。

例えば、a = 1、b = 7、c = 3 の場合、数列は「1, 4, 7, 10, …」となります。この中に 7 は含まれているため、出力は「Yes」になります。

判定の考え方

この問題は、次の2つのケースに分けて考えることで解くことができます。

• c = 0 の場合: 数列のすべての項は a と等しくなります。したがって、a = b であれば「Yes」を出力し、a ≠ b であれば「No」を返します。
• c > 0 の場合: ある非負の整数 k に対して b = a + k × c が成り立てば、b は数列に含まれることになります。これは「(b − a) が c の倍数であり、かつ b − a ≥ 0 である」と言い換えられます。つまり、(b − a) / c が非負の整数になればよいのです。

C++での実装例

上記の考え方をもとに、C++で実装すると以下のようになります。

#include<iostream>
using namespace std;
void isBInSequence(int a, int b, int c){
    if (a == b)
        cout << "Yes";
    if ((b - a) * c > 0 && (b - a) % c == 0)
        cout << "Yes";
    else
        cout << "No";
}
int main() {
    int a = 1, b = 7, c = 3;
    cout << "The answer is: ";
    isBInSequence(a, b, c);
}

実行結果

The answer is: Yes

このように、剰余演算と符号の判定を組み合わせることで、無限に続く数列であっても O(1) の計算量で b の存在を効率的に判定できます。等差数列の性質を理解していれば、実際に数列を生成して順に比較する必要はありません。