概要

与えられた範囲 \([L, R]\) の整数のうち、各桁の数字の積が \(K\) となるものの個数を求める問題です。 桁DP（桁数に関する動的計画法）を用いて、範囲 \([1, X]\) に対するクエリを解く問題に帰着させて解きます。

考察

1. 範囲 \([L, R]\) の扱い

典型的なテクニックとして、区間 \([L, R]\) における条件を満たす整数の個数は、\([1, R]\) における個数から \([1, L-1]\) における個数を引くことで求められます。 したがって、 \(1\) 以上 \(X\) 以下の整数で \(f(n) = K\) を満たすものの個数を求める関数 \(\text{solve}(X)\) を実装すれば、答えは \(\text{solve}(R) - \text{solve}(L-1)\) となります。

2. \(K = 0\) の場合

\(f(n) = 0\) となるのは、少なくとも \(1\) つの桁に \(0\) が含まれる場合です。 これは「すべての桁が \(1\) から \(9\) であるものの個数」を全体から引くことで求められます。 \(1\) 以上 \(X\) 以下の整数のうち、すべての桁が \(1\) から \(9\) である（\(0\) を一度も使わない）ものの個数は、簡単な桁DPで求められます。 \(1\) 以上 \(X\) 以下の整数の総数は \(X\) なので、 \(f(n) = 0\) となるものの個数は \(X - (\text{0 を含まないものの個数})\) と計算できます。

3. \(K > 0\) の場合

\(K > 0\) の場合、各桁に \(0\) を含めることはできません（\(0\) が含まれると積が \(0\) になってしまうため）。 よって、各桁の数字は \(1\) から \(9\) のいずれかです。 このとき、各桁の数字の積である \(K\) の素因数は \(2, 3, 5, 7\) のいずれかでなければなりません。 もし \(K\) がこれら以外の素因数（例えば \(11\) や \(13\) など）を持つ場合、 \(f(n) = K\) となる \(n\) は存在しないため、答えは \(0\) となります。

\(K\) の素因数が \(2, 3, 5, 7\) のみである場合、各桁の数字を決定していく過程で、「これまでに決めた桁の積」が \(K\) の約数である必要があります。また、残りの桁で達成すべき積も \(K\) の約数になります。 \(K \le 10^{18}\) において、素因数が \(2, 3, 5, 7\) のみであるような \(K\) の約数の個数は、最大でも \(60,000\) 個程度と非常に少ないです。 この性質を利用して、状態に「残りの必要な積（\(K\) の約数のインデックス）」を持たせた桁DPを行うことができます。

アルゴリズム

1. \(K\) の約数の列挙と遷移テーブルの作成

まず、 \(K\) を \(2, 3, 5, 7\) で素因数分解し、それ以外の素因数があれば \(0\) を出力して終了します。 \(K\) の約数をすべて列挙し、昇順にソートします。 各約数 \(v\) について、 \(1 \le d \le 9\) の数字で割ったとき、 \(v\) が \(d\) で割り切れ、かつその商 \(v/d\) も \(K\) の約数に含まれる場合、その遷移先（約数のインデックス）を事前に計算しておきます（next_div テーブル）。

2. 桁DPの設計

\(1\) 以上 \(X\) 以下の整数について、上から \(i\) 桁目まで決めたときの状態を以下のように定義します。 dfs(idx, is_less, is_started, div_idx) - idx: 現在見ている桁（\(0\) から \(N-1\)、ただし \(N\) は \(X\) の桁数） - is_less: \(X\) より小さいことが確定しているか（true / false） - is_started: すでに \(1\) 以上の数字を配置し始めているか（リーディングゼロの処理、true / false） - div_idx: 残りの桁で達成すべき積を表す \(K\) の約数のインデックス

遷移：

1. まだ数字を配置し始めていない場合 (!is_started): 現在の桁をスキップして次の桁に進むことができます（実質的にリーディングゼロを無視する）。 dfs(idx + 1, true, false, div_idx) へ遷移します。
2. 数字 \(d \in [1, limit]\) を配置する場合: ここで \(limit\) は、is_less が true なら \(9\)、false なら \(X\) の idx 桁目の数字です。 現在の必要な積 \(divs[div\_idx]\) が \(d\) で割り切れる場合、次の状態は dfs(idx + 1, is_less || (d < limit), true, nxt_div_idx) となります。ここで nxt_div_idx は \(divs[div\_idx] / d\) のインデックスです。

ベースケース：

idx == N（すべての桁を決定したとき）に、is_started が true かつ divs[div_idx] == 1（必要な積をすべて達成した）であれば \(1\) を返し、そうでなければ \(0\) を返します。

これをメモ化再帰で実装することで、高速に求めることができます。

計算量

• 時間計算量: \(O(N \times D + D \log D)\) \(K\) の約数の個数を \(D\) とします。\(K \le 10^{18}\) において \(D \le 60,000\) です。 桁DPの状態数は \(O(N \times D)\)（ここで \(N = \log_{10} R \le 18\)）です。各状態からの遷移は \(1\) から \(9\) の \(9\) 通りなので、DP全体の計算量は \(O(N \times D)\) です。 約数の列挙や遷移テーブルの作成も \(O(D \log D)\) 程度で十分高速です。全体として、実行時間制限に十分間に合います。

• 空間計算量: \(O(N \times D)\) メモ化用の配列のサイズは \(O(N \times D)\) です。約数リストや遷移テーブルのサイズも \(O(D)\) であり、全体として数メガバイト程度に収まります。

実装のポイント

• 約数の高速な検索: DPの遷移の中で約数のインデックスを求める際、毎回二分探索 (std::lower_bound) を行うと重くなるため、あらかじめ next_div[div_idx][d] として遷移先をテーブル化しておくことで、DP本体を高速化しています。

• メモ化配列の1次元化: 多次元の std::vector は動的確保のオーバーヘッドが大きいため、状態を1次元のインデックスにマッピングした1次元配列を使用することで、メモリ効率と実行速度を向上させています。

  ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// f(n) = 0 となるものの個数を求めるための、すべての桁が 1-9 であるものの個数
long long solve_h(long long X) {
    if (X <= 0) return 0;
    string S = to_string(X);
    int n = S.size();
    vector memo(n, vector(2, vector<long long>(2, -1)));
    auto dfs = [&](auto& self, int idx, bool is_less, bool is_started) -> long long {
        if (idx == n) {
            return is_started ? 1 : 0;
        }
        if (memo[idx][is_less][is_started] != -1) {
            return memo[idx][is_less][is_started];
        }
        long long res = 0;
        if (!is_started) {
            res += self(self, idx + 1, true, false);
        }
        int limit = is_less ? 9 : (S[idx] - '0');
        for (int d = 1; d <= limit; ++d) {
            res += self(self, idx + 1, is_less || (d < limit), true);
        }
        return memo[idx][is_less][is_started] = res;
    };
    return dfs(dfs, 0, false, false);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long L, R, K;
    if (!(cin >> L >> R >> K)) return 0;

    if (K == 0) {
        long long ans = (R - solve_h(R)) - ((L - 1) - solve_h(L - 1));
        cout << ans << "\n";
        return 0;
    }

    // K > 0 の場合
    // 素因数分解
    long long temp = K;
    int A = 0, B = 0, C = 0, D = 0;
    while (temp % 2 == 0) { temp /= 2; A++; }
    while (temp % 3 == 0) { temp /= 3; B++; }
    while (temp % 5 == 0) { temp /= 5; C++; }
    while (temp % 7 == 0) { temp /= 7; D++; }

    if (temp > 1) {
        cout << 0 << "\n";
        return 0;
    }

    // 約数の列挙
    vector<long long> divs;
    long long p2 = 1;
    for (int a = 0; a <= A; ++a) {
        long long p3 = p2;
        for (int b = 0; b <= B; ++b) {
            long long p5 = p3;
            for (int c = 0; c <= C; ++c) {
                long long p7 = p5;
                for (int d = 0; d <= D; ++d) {
                    divs.push_back(p7);
                    if (D - d > 0 && p7 > K / 7) break;
                    p7 *= 7;
                }
                if (C - c > 0 && p5 > K / 5) break;
                p5 *= 5;
            }
            if (B - b > 0 && p3 > K / 3) break;
            p3 *= 3;
        }
        if (A - a > 0 && p2 > K / 2) break;
        p2 *= 2;
    }
    sort(divs.begin(), divs.end());
    int num_divs = divs.size();

    vector<vector<int>> next_div(num_divs, vector<int>(10, -1));
    for (int i = 0; i < num_divs; ++i) {
        long long val = divs[i];
        for (int d = 1; d <= 9; ++d) {
            if (val % d == 0) {
                long long target = val / d;
                auto it = lower_bound(divs.begin(), divs.end(), target);
                if (it != divs.end() && *it == target) {
                    next_div[i][d] = distance(divs.begin(), it);
                }
            }
        }
    }

    auto solve = [&](long long X) -> long long {
        if (X <= 0) return 0;
        string S = to_string(X);
        int n = S.size();
        int state_size = n * 4 * num_divs;
        vector<long long> memo(state_size, -1);

        auto get_memo_idx = [&](int idx, bool is_less, bool is_started, int div_idx) {
            return ((idx * 2 + is_less) * 2 + is_started) * num_divs + div_idx;
        };

        auto dfs = [&](auto& self, int idx, bool is_less, bool is_started, int div_idx) -> long long {
            if (idx == n) {
                if (is_started && divs[div_idx] == 1) return 1;
                return 0;
            }
            int memo_idx = get_memo_idx(idx, is_less, is_started, div_idx);
            if (memo[memo_idx] != -1) {
                return memo[memo_idx];
            }

            long long res = 0;
            if (!is_started) {
                res += self(self, idx + 1, true, false, div_idx);
            }

            int limit = is_less ? 9 : (S[idx] - '0');
            for (int d = 1; d <= limit; ++d) {
                int nxt_div_idx = next_div[div_idx][d];
                if (nxt_div_idx != -1) {
                    res += self(self, idx + 1, is_less || (d < limit), true, nxt_div_idx);
                }
            }
            return memo[memo_idx] = res;
        };

        return dfs(dfs, 0, false, false, num_divs - 1);
    };

    long long ans = solve(R) - solve(L - 1);
    cout << ans << "\n";

    return 0;
}

---

この解説は gemini-3.5-flash-thinking によって生成されました。