C++で積と和の差が指定値DとなるN個の整数を見つける方法

問題の概要

2つの整数NとDが与えられたとき、それらの合計と積の差がちょうどDと等しくなるような、N個の整数の集合を見つける必要があります。

例えば、N=3、D=5の場合、答えは「1, 2, 8」です。このとき合計は 1 + 2 + 8 = 11、積は 1 × 2 × 8 = 16 となり、16と11の差はちょうど5（= D）になります。

解法のアプローチ：巧妙な構成テクニック

この問題を効率的に解くには、次のような構成を利用します。

• N−2個の「1」
• 1つの「2」
• 残りの1つとして「N + D」

この構成を採用すると、合計・積・差はそれぞれ以下のように計算できます。

• 合計 = (N − 2) × 1 + 2 + (N + D) = 2N + D
• 積 = (N − 2) × 1 × 2 × (N + D) = 2N + 2D
• 差 = (2N + 2D) − (2N + D) = D

このように、与えられるNとDの値が何であっても、この構成方法を使えば必ず条件を満たす整数の集合を得られることが数学的に保証されます。探索を行う必要がないため、計算量はO(N)と非常に効率的です。

C++での実装例

#include<iostream>
using namespace std;

void getNNumbers(int n, int d) {
    // N-2個の1を出力
    for (int i = 0; i < n - 2; i++)
        cout << 1 << " ";
    // 2を出力
    cout << 2 << " ";
    // N + D を出力
    cout << n + d << endl;
}

int main() {
    int N = 5, D = 8;
    getNNumbers(N, D);
}

出力結果

1 1 1 2 13

N=5、D=8の場合の出力は「1 1 1 2 13」です。検証してみると、合計は 1 + 1 + 1 + 2 + 13 = 18、積は 1 × 1 × 1 × 2 × 13 = 26 となり、その差は 26 − 18 = 8 で、確かにDと一致しています。

まとめ

本問題は、一見すると複雑な組み合わせ探索が必要に思えますが、「1を複数個使うと積に影響しない」という性質を利用することで、シンプルな公式ベースの解法に帰着できます。競技プログラミングなどで役立つ定番テクニックの一つなので、ぜひ覚えておきましょう。