Pythonで素敵な約数の個数を最大化するプログラムの解説

問題の概要

整数 pf(素因数の個数)が与えられます。ここで、次の条件を満たす正の整数 n を構成することを考えます。

• n の素因数の個数(重複していてもよい)は pf 以下であること
• n の「素敵な約数(nice divisor)」の個数が最大になること。素敵な約数とは、n のすべての素因数で割り切れる約数のことです。

求めたいのは、そのような n における素敵な約数の個数です。答えが非常に大きくなる可能性があるため、結果は 10^9 + 7 で割った余りとして返します。

例えば、入力が pf = 5 のとき、出力は 6 になります。n = 200 とすると、素因数は [2, 2, 2, 5, 5] であり、素敵な約数は [10, 20, 40, 50, 100, 200] の 6 個となるからです。

解法のアプローチ

この問題は、次の手順で解くことができます。

• pf が 1 の場合は、1 を返します。
• m := 10^9 + 7 とします。
• q := pf ÷ 3 の商、r := pf を 3 で割った余り とします。
• r == 0 の場合:3^q mod m を返します。
• r == 1 の場合:(3^(q-1) mod m) × 4 mod m を返します。
• 上記以外(r == 2)の場合:(3^q mod m) × 2 mod m を返します。

なぜこれで最適になるのか?

このアルゴリズムの背後にある考え方を整理しておきましょう。n を素因数分解して p1^e1 × p2^e2 × … × pk^ek と表すと、すべての素因数で割り切れる約数(素敵な約数)は p1^a1 × … × pk^ak(各 ai は 1 以上 ei 以下)の形をした数なので、その個数は e1 × e2 × … × ek になります。

つまり、この問題は「指数の合計が pf 以下という制約のもとで、指数の積を最大化せよ」という整数の分割(integer break)問題に帰着します。和が固定されたときに積を最大化するには、できる限り 3 で分割するのが最適であり、余りの処理だけ場合分けすればよいのです。

• 余りが 0:すべて 3 の積にできる
• 余りが 1:3 を一つ取り除いて 4(= 2 + 2)に置き換える方が得
• 余りが 2:最後に 2 を掛ける

Pythonによる実装例

理解を深めるために、実際の実装コードを見てみましょう。

def solve(pf):
    if pf == 1:
        return 1
    m = 10**9 + 7
    q, r = divmod(pf, 3)
    if r == 0:
        return pow(3, q, m)
    elif r == 1:
        return pow(3, q - 1, m) * 4 % m
    else:
        return pow(3, q, m) * 2 % m

pf = 5
print(solve(pf))

入力

5

出力

6

まとめ

素因数の個数 pf が与えられたとき、素敵な約数の個数を最大化する問題は、指数の積の最大化問題に帰着できます。3 を基数とした分割戦略(余りに応じて 4 や 2 を組み合わせる)を採用することで、べき乗計算のみで O(log pf) の計算量という非常に効率的な解法を実現できる点がポイントです。