C++でNを1に減らすための最大操作回数を見つける方法

概念

2つの整数 P と Q(いずれも最大 10⁶)が与えられ、そこから N = P!/Q! という数が構成されます。この課題の目標は、実行可能な限り多くの操作を繰り返して N を 1 まで減らすことです。ただし、1回の操作では「N がある数 X で割り切れる場合に、N を N/X で置き換える」ことしかできません。このとき実現できる操作回数の最大値を求めます。

入出力例

例 1

入力:

A = 7, B = 4

出力:

4

説明: N は 210 となり、素因数は 2・3・5・7 の 4 個です。それぞれで順に割ることで、ちょうど 4 回の操作で 1 になります。

例 2

入力:

A = 3, B = 1

出力:

2

説明: N は 6 となり、素因数は 2・3 の 2 個です。

解法のアプローチ

P!/Q! を因数分解した結果は、(Q + 1) × (Q + 2) × … × (P − 1) × P をそれぞれ個別に因数分解した結果と一致します。

さらに重要な点として、操作回数を最大化するには、N を素因数だけで割るのが最適です。合成数でまとめて割ってしまうと操作回数を無駄に損することになるため、結局「重複を含む N の素因数の総個数」を求めればよいことになります。

そこで、2 から 1,000,000 までの各整数について、素因数の個数をあらかじめ数えておきます。まずはエラトステネスの篩(Sieve of Eratosthenes)を応用して、各数の素因数を特定します。手順は以下の通りです。

• 2 から N までの連続する整数のリスト (2, 3, 4, …, N) を作成します。
• まず p を最初の素数である 2 とします。
• p² から開始して p ずつ増加させながら、リスト内の該当する数(p×(p+1)、p×(p+2)、p×(p+3) など)にすべて印を付けます。
• リスト内で p より大きく、まだ印の付いていない最初の数を探します。そのような数が存在しなければ終了します。存在する場合は、その数(次の素数)を新たな p とみなし、手順 3 から繰り返します。

エラトステネスの篩を適用した後は、次の漸化式によって各数の素因数の個数を計算できます。

primefactors[num] = primefactors[num / primedivisor[num]] + 1

さらに、素因数の個数に関する累積和(プレフィックスサム)配列を構築しておけば、区間 [Q, P] に含まれる素因数の総数を、端点同士の差分という 1 回の計算で即座に求められます。これにより、複数のテストケースがあっても高速に対応できます。

C++による実装例

// 最大操作回数を求める C++ プログラム
#include <bits/stdc++.h>
using namespace std;
#define N 1000005

// 各数の素因数の個数を格納する配列
int primeFactors1[N];

// 各数の素因数の個数を求める関数
void findPrimeFactors() {
    for (int a = 2; a < N; a++)
        // a が素数の場合
        if (primeFactors1[a] == 0)
            for (int b = a; b < N; b += a)
                // 直近の倍数の値に 1 を加えて更新
                primeFactors1[b] = primeFactors1[b / a] + 1;

    // 累積和を構築(複数テストケースで有効)
    for (int a = 1; a < N; a++)
        primeFactors1[a] += primeFactors1[a - 1];
}

// ドライバーコード
int main() {
    // primeFactors1 配列を生成
    findPrimeFactors();
    int P = 7, Q = 4;
    // 求める答えを出力
    cout << primeFactors1[P] - primeFactors1[Q];
    return 0;
}

出力

4

まとめ

本問のポイントは、「N = P!/Q! を 1 にする最大操作回数は、重複込みの素因数の総個数に等しい」という変換に気づくことです。エラトステネスの篩の要領で各数の素因数の個数を前計算し、累積和を持っておけば、任意の区間 [Q, P] に対する答えを O(1) で取得できます。前計算の計算量は O(N log log N) 程度、必要なメモリは O(N) であり、上限が 10⁶ の制約下でも十分高速に動作します。