与えられた正整数 N を、互いに異なる複数の自然数に分解し、それらの自然数の積が最大となるようにする方法について解説します。分解された自然数は昇順で表示し、その最大積も計算・表示します。この問題は、効率的な貪欲法と高精度計算を組み合わせることで解決できます。

問題の概要

正整数 N (3 ≤ N ≤ 10000) が与えられます。N を互いに異なる自然数（ただし 1 を除く）の和として表現し、それらの自然数の積が最大となる組み合わせを見つけてください。

例: N = 10

• 考えられる分解の例:
  • 1+2+3+4 = 10 (積 24)
  • 2+3+5 = 10 (積 30)
  • 1+4+5 = 10 (積 20)
• この場合、最適な分解は 2, 3, 5 であり、最大積は 30 となります。

基本的な考え方とアルゴリズム

積を最大化するためには、以下の原則が重要です。

1. 1 を使用しない: どのような自然数 x に対しても、1 × x = x となり、1 を因数に含めても積は増加しません。また、x を 1 と x-1 に分解するよりは、x のままか、より有効な他の分解を検討すべきです。
2. なるべく多くの数に分解する: 一般的に、同じ合計値を持つ複数の数の積は、より多くの数を因子に持つ場合の方が大きくなる傾向があります。例えば、6 をそのまま使う（積 6）よりも、2+4 に分解する（積 8）方が大きくなります。（ただし、ここでも 1 を使わないという制約を守る必要があります。）
3. 小さい数から順に採用する (貪欲法): 上記の原則に基づき、積を最大化するには、可能な限り小さい互いに異なる自然数（2, 3, 4, ...）から順に選んでいく「貪欲法」が有効です。これにより、分解される因数の数を最大化しやすくなります。

アルゴリズムの詳細ステップ

以下の手順で、N を分割する自然数のリストを作成します。

1. 初期因数の選定:

   まず、k=2 から始め、N を超えない範囲で、連続する自然数 2, 3, 4, ... を加算していきます。選んだ数は factors_map という配列にマークしておきます。

   int current_total = 0;
   int factors_map[10001] = {0}; // factors_map[i] = 1 なら i が選ばれている
   int current_factor = 2; // 次に選ぶべき自然数の候補
   
   // N を超えない範囲で小さい数から順に選択
   while (current_total + current_factor <= N_val) {
       factors_map[current_factor] = 1;
       current_total += current_factor;
       current_factor++;
   }
   // この時点で current_factor は、合計が N_val を超える最初の候補値になっている
   // factors_map には 2, 3, ..., (current_factor - 1) が選ばれている
   

2. 残りの値 (余り) の処理:

   上記のステップで選んだ数の合計 current_total と N_val との差を remaining_value = N_val - current_total とします。

   この remaining_value を、既存の因数に「1ずつ」加算していくことで分配するのが一般的です。積を最大化するためには、大きい数に加算する方が有利ですが、この問題では因数が「互いに異なる」という制約があるため、単に1ずつ加算するだけでは不十分です。

   ここでは、効率的な特殊処理を行います。

   • ケース1: (current_factor - remaining_value) >= 2 の場合

     これは、remaining_value が比較的小さく、既存の因数 (current_factor - remaining_value) をリストから除外し、その代わりに次の候補値 current_factor をリストに追加できることを意味します。これにより、因数の数は維持され、より大きい因数が導入されるため積が増加します。

     例: N=10

     • 初期選定: {2, 3, 4} (合計9)
     • current_factor: 5
     • remaining_value: 10 - 9 = 1
     • current_factor - remaining_value = 5 - 1 = 4。これは ≥ 2 なのでケース1に該当。
     • factors_map[4] を 0 にして削除し、factors_map[5] を 1 にして追加。
     • 結果: {2, 3, 5}

     if (current_factor - remaining_value >= 2) {
         // 既存の因数 (current_factor - remaining_value) を削除し、current_factor を追加
         factors_map[current_factor - remaining_value] = 0; // 削除
         factors_map[current_factor] = 1; // 追加
     }
     

   • ケース2: (current_factor - remaining_value) < 2 の場合

     これは、remaining_value が大きく、(current_factor - remaining_value) が 1 以下になってしまう状況です。この場合、1 を使わないという制約を守るため、最小の因数である 2 をリストから削除し、その 2 の値と remaining_value を合わせて、新しい因数 2 + remaining_value を生成します。この新しい因数は既存のどの因数とも重ならないように配置されます。

     例: N=8

     • 初期選定: {2, 3} (合計5)
     • current_factor: 4
     • remaining_value: 8 - 5 = 3
     • current_factor - remaining_value = 4 - 3 = 1。これは < 2 なのでケース2に該当。
     • factors_map[2] を 0 にして削除し、factors_map[2 + remaining_value] (つまり factors_map[5]) を 1 にして追加。
     • 結果: {3, 5}

     else {
         // 最小の因数である 2 を削除し、(2 + remaining_value) を新しい因数として追加
         factors_map[2] = 0; // 2 を削除
         factors_map[2 + remaining_value] = 1; // 新しい因数 (2 + remaining_value) を追加
     }
     

高精度計算の実装

Nが10000の場合、因数の積は非常に大きな数となり、標準的な整数型 (int, long long など) では表現しきれずオーバーフローしてしまいます。そのため、文字列や配列を使って各桁を保持する「高精度計算」が必要です。

ここでは、各桁を整数配列に格納し、通常の筆算のように計算を進める方法を採用します。product_digits[0] が1の位、product_digits[1] が10の位となるように格納します。乗算を行うたびに、桁上がり (キャリー) を処理し、必要に応じて配列の桁数を増やしていきます。

#include <stdio.h>
#include <string.h> // memset のために必要

// N=10000 の場合、積は数百桁になる可能性があるため、十分なサイズを確保
#define MAX_DIGITS 5000 

int product_digits[MAX_DIGITS]; // 各桁を格納する配列 (product_digits[0] は1の位)
int num_digits; // 現在の有効な桁数

// 高精度積 product_digits に factor を乗算する関数
void multiply_big_int(int factor) {
    int carry = 0;
    // 各桁に factor を乗算し、桁上がりを処理
    for (int i = 0; i < num_digits; ++i) {
        long long temp = (long long)product_digits[i] * factor + carry;
        product_digits[i] = temp % 10; // 現在の桁の値
        carry = temp / 10;             // 次の桁への桁上がり
    }
    // 残りの桁上がりを処理し、必要に応じて桁数を増やす
    while (carry > 0) {
        // 配列の最大サイズを超えないかチェック（理論上は発生しないはずだが安全のため）
        if (num_digits >= MAX_DIGITS) {
            fprintf(stderr, "エラー: 最大桁数を超過しました。\n");
            return; 
        }
        product_digits[num_digits++] = carry % 10;
        carry /= 10;
    }
}

int main() {
    int N_val;
    scanf("%d", &N_val);

    int factors_map[10001] = {0}; // factors_map[i] = 1 なら i が選ばれている
    int current_total = 0;        // 現在の因数合計
    int current_factor = 2;       // 次に選ぶべき自然数の候補

    // ステップ1: 小さい数から順に N_val を超えない範囲で因数を選定
    while (current_total + current_factor <= N_val) {
        factors_map[current_factor] = 1; // current_factor を選ぶ
        current_total += current_factor;
        current_factor++; // 次の候補へ
    }
    // ループ終了時、current_factor は N_val を超える最初の候補数になっている

    // ステップ2: 残りの値 (余り) の処理
    int remaining_value = N_val - current_total;

    if (remaining_value > 0) { // 余りがある場合のみ処理
        if (current_factor - remaining_value >= 2) {
            // ケース1: 既存の因数 (current_factor - remaining_value) を削除し、
            // 新しい因数 current_factor を追加
            factors_map[current_factor - remaining_value] = 0;
            factors_map[current_factor] = 1;
        } else {
            // ケース2: 最小の因数である 2 を削除し、
            // 新しい因数 (2 + remaining_value) を追加
            factors_map[2] = 0;
            factors_map[2 + remaining_value] = 1;
        }
    }

    // 最大積の計算のため、product_digits を 1 で初期化
    // memset で全ての要素を 0 にクリアし、product_digits[0] (1の位) を 1 に設定
    memset(product_digits, 0, sizeof(product_digits));
    product_digits[0] = 1;
    num_digits = 1; // 初期状態では 1桁 (値は 1)

    // 選ばれた因数を昇順で出力し、高精度積を計算
    for (int j = 2; j <= N_val + remaining_value; ++j) { // 最大で N_val+remaining_value の因数が存在しうる
        if (factors_map[j] == 1) {
            printf("%d ", j);
            multiply_big_int(j); // 高精度乗算を実行
        }
    }
    printf("\n"); // 因数リストの出力後に改行

    // 計算された最大積を逆順に出力 (product_digits は逆順に格納されているため)
    for (int i = num_digits - 1; i >= 0; --i) {
        printf("%d", product_digits[i]);
    }
    printf("\n"); // 最大積の出力後に改行

    return 0;
}