C++で数値が2つの三角数の和として表現できるか判定する方法

本記事では、ある整数が2つの三角数の和として表現できるかどうかを判定する方法を、C++のコード例とともに分かりやすく解説します。

三角数とは

三角数とは、1、3、6、10、15…のように、1から順に自然数を加算して得られる数列のことです。点を正三角形の形に並べたときの個数に対応することから「三角数」と呼ばれています。n番目の三角数は次の式で求められます。

n × (n + 1) / 2

例えば、1、3、6、10などが三角数に該当します。これらを利用すると、16は「6 + 10」という2つの三角数の和として表現できます。

判定アルゴリズム

判定の手順は非常にシンプルです。

1. N未満のすべての三角数を生成し、セット(std::set)に格納します。
2. セット内の各値Xについて、「N − X」が同じセット内に存在するかどうかを調べます。
3. 存在すれば、NはXと(N − X)という2つの三角数の和で表せるため、trueを返します。

この方法なら、全ペアを総当たりする必要がなく、セットの高速な検索機能を活かして効率的に判定できます。

C++での実装例

#include <iostream>
#include <set>
using namespace std;
bool isSumTriangularNum(int n) {
    set<int> s;
    int i = 1;
    while (1) { // n未満の三角数をすべて求めてセットに格納
        int x = i * (i + 1) / 2;
        if (x >= n)
            break;
        s.insert(x);
        i++;
    }
    for (auto x : s)
    if (s.find(n - x) != s.end())
    return true;
    return false;
}
int main() {
    int num = 16;
    if(isSumTriangularNum(num)){
        cout << "Can be represented";
    }else{
        cout << "Cannot be represented";
    }
}

実行結果

Can be represented

この例では16を渡しているため、「6 + 10」という組み合わせが見つかり、「Can be represented(表現可能)」と出力されます。もし表現できない数(例えば2や4など)を渡した場合は「Cannot be represented」と表示されます。

計算量について

N未満の三角数の個数はおよそ√N個であるため、生成処理はO(√N)で完了します。さらに、std::setへの挿入・検索はそれぞれO(log N)で行えるため、アルゴリズム全体の計算量は約O(√N log N)となります。Nが大きな値でも高速に判定できるのがこの手法の強みです。