【C++】1からnまでの自然数を、指定した差と互いに素な合計を持つ2つの集合に分割できるか判定する方法

このチュートリアルでは、1からnまでの自然数を、次の条件を満たす2つのグループに分割できるかどうかを判定する方法を解説します。

• 2つのグループの合計値の絶対差が、与えられた値mと一致すること
• 2つの合計値の最大公約数（GCD）が1であること、つまり両者が互いに素（コプライム）であること

考え方：数式によるアプローチ

最初のn個の自然数の合計は、有名な公式 (n × (n + 1)) / 2 で求められます。全体の合計と目標となる差mが分かれば、連立方程式を解くことで、それぞれのグループの合計（sumOne・sumTwo）を簡単に導き出すことができます。

sumOne + sumTwo = (n*(n+1))/2
sumOne - sumTwo = m

この2式を組み合わせることで、sumOne = (total_sum + m) / 2、sumTwo = total_sum − sumOne として計算できます。

C++での実装例

実装の手順はシンプルです。まず、合計の絶対差がmと等しいかどうかを確認し、その後、2つの合計値のGCDが1になっているかをチェックします。

#include <bits/stdc++.h>
using namespace std;
bool canSplitIntoTwoHalves(int n, int m) {
    int total_sum = (n * (n + 1)) / 2;
    int sumOne = (total_sum + m) / 2;
    int sumTwo = total_sum - sumOne;
    if (total_sum < m) {
        return false;
    }
    if (sumOne + sumTwo == total_sum && sumOne - sumTwo == m) {
        return (__gcd(sumOne, sumTwo) == 1);
    }
    return false;
}
int main() {
    int n = 10, m = 17;
    if (canSplitIntoTwoHalves(n, m)) {
        cout << "Can split";
    }
    else {
        cout << "Can't split";
    }
    return 0;
}

実行結果

上記のコードを実行すると、次のような出力が得られます。

Can split

この例では n = 10、m = 17 を指定しています。1から10までの合計は55となり、sumOne = 36、sumTwo = 19 に分割でき、差は17、さらに GCD(36, 19) = 1 となるため「分割可能」と判定されます。

まとめ

本記事では、1からnまでの自然数を、合計の差がmで互いに素となる2つの集合に分割できるかを判定するアルゴリズムを紹介しました。ポイントは、等差数列の和の公式と連立方程式を使って各グループの合計を求め、__gcd 関数で互いに素であることを確認する点です。同様の問題に取り組む際の参考にしてみてください。

チュートリアルの内容についてご質問がある場合は、ぜひコメント欄でお知らせください。