この解説は大きく分けて二つの部分に分かれています。

• 前半では \(N\) の計算量への寄与を \(\mathrm{O}(N)\) から \(\mathrm{O}(\log N)\) に落とすアルゴリズム(桁DP)を説明しています。
• 後半ではさらに \(\mathrm{O}(K \log N)\) から \(\mathrm{O}((\log K)^4 \log N)\) に削減する方法を説明します。

1. 桁 DP

このような問題では、整数を具体的に1つずつ挙げて愚直に計算すると少なくとも \(\mathrm{O}(N)\) 程度の計算量になってしまいます。問題文の \(N \leq 10^{18}\) という制約からもわかる通り、 \(N\) に対して線形時間よりも高速なアルゴリズムを構築する必要があります。

\(N\) 以下の整数のうち、桁によって条件付けが為された整数の個数を高速に数える手法としては、桁DPと呼ばれる手法が有名です。

桁 DP とは、値の上から \(i\) 桁目までを確定させたときに、\(N\) 未満で確定しているかどうかを状態に加えた DP を指します。

• 桁 DP に関する詳細な説明はインターネット上に多くの解説が載っているのでここでは割愛します。 桁 DP に関して知りたい方は桁 DP の解説がなされたホームページをご参照ください。

桁 DP を利用してこの問題を解くことを考えます。状態の持ち方はいくつか考えられますが、ここでは DP の状態として、

• \(\mathrm{dp} _{i, p} := \) (上から \(i\) 桁目までが \(\bf 0\) 以外で確定していて、確定している桁の総積が \(p\) である場合の数)

と置きます。また、\(\mathrm{eq}_{i} :=\) ( \(N\) の上から \(i\) 桁目までの総積 ) とおきます。すると、以下の疑似コードで説明されるDPの遷移が成り立ちます。(注:以下の疑似コードをそのまま実装すると TLE, MLE してしまいます。)

# Python風の疑似コード
# for i in range(a, b) は「変数iをaからb-1まで変化させる」という意味

# input : N, K
# output : answer
def calc(N, K):
  dp = (全て0で初期化された2次元配列)
  eq = (全て0で初期化された1次元配列)

  eq[0] = 1

  for i in range(1, Nの桁数 + 1):
    # Nのi桁目をdigitとする
    digit = (Nの上からi桁目)

    # (1) less -> less
    # i-1桁目までがNのi-1桁目までと比べて小さい場合
    # i桁目の数dは0以上9以下がOK
    for p in range(0, dp[i]の長さ)
      for d in range(0, 10):
        dp[i + 1][p * d] += dp[i][p]

    # (2) equal -> less
    #  i-1桁目までがNと同じで、かつi桁目がNのi桁目より小さい場合
    # i桁目の数dは0以上digit未満がOK
    for d in range(0, digit):
      # i = 0 かつ d = 0 の時は全体が0になってしまうため除外
      if i == 0 and d == 0:
        continue
      dp[i + 1][eq[i] * d] += 1

    # (3) equal -> equal
    # i桁目までNと一致する時
    # i桁目の数はdigit
    eq[i + 1] = eq[i] * digit

    # (4) 0...0d 型
    # i-1桁目までが0でi桁目が0以外の時
    # i桁目の数dは1以上9以下がOK
    # (d = 0の時は全体が0になってしまうため除外)
    for d in range(1, 10):
      # i = 0 の場合は(2)ですでにカウントしている
      if i == 0:
        continue
      dp[i + 1][d] += 1

  answer =  0
  for p in range(0, dp[(Nの桁数)]の長さ):
    if p <= K:
      answer += dp[(Nの桁数)][p]

  if eq[(Nの桁数)] <= K:
    answer += 1

  return ans

2. 状態数削減を利用した高速化

桁 DP の導入によってこの問題を \(N\) に対しての線形時間アルゴリズムから対数時間アルゴリズムへと高速化することが出来ました。しかしこのままでは DP の状態数が爆発的な量になってしまうので AC することが出来ません。

このような DP の高速化を行う際の基本テクニックとして問題が持つ性質を利用して DP の状態数を削減するというテクニックがあります。このテクニックを利用して状態数を減らしてみましょう。

まず、この問題は積が \(K\) 以下かどうかで場合分けを行う問題なので、 \(p\) が \(K\) より大きい場合の状態は同一視してよいとわかります。よって

• 桁の数字の積が \(0\) である
• 桁の数字の積が \(1,2,\dots,K\) である
• 桁の数字の積が \(K+1\) 以上である

の \(3\) つに場合分けをすれば \(K+2\) 個の状態を持って DP をすることが出来ます。このように状態数を \(\mathrm{O}(K)\) にすることで基数を \(B=10\) とおいて \(\mathrm{O}(K B \log N)\) で答えを計算できるアルゴリズムを構成できますが、この解法でも TLE してしまいます。

さらに状態数を削減するために、桁の総積 \(p\) の持つ性質に注目します。\(p\) の値は \(0\) または \(1,2,\dots,9\) の積で表せますが、 \(0\) を除くと整数 \(1,\dots,9\) は \(2,3,5,7\) のみを素因数に持ちます。すると、 \(N\) 以下の整数の各桁の数字の積 \(p\) は、

\[p=0\ または\ p=2^a \cdot 3^b \cdot 5^c \cdot 7^d\]

で表せると分かります。

この事実を利用すると、必要な状態数を \(\mathrm{O}(K)\) から削減することが出来ます。 \(p\) が \(K\) より大きい場合は状態に持たなくて良いので、 \(p = 2^a \cdot 3^b \cdot 5^c \cdot 7^d \leq K\) という関係式が成り立ちます。この条件を満たす \(a,b,c,d\) の個数のオーダーを考えると、 \(a,b,c,d\) は次の不等式

\[ 0 \leq a \leq \log_2 K,\ 0 \leq b \leq \log_3 K ,\ 0 \leq c \leq \log_5 K,\ 0 \leq d \leq \log_7 K \]

を満たす必要があるので、状態数は高々 \(\mathrm{O}(\log_2 K \log_3 K \log_5 K \log_7 K) = \mathrm{O}( (\log K)^4 )\) で抑えられます。(実際は \(a+b+c+d\) が \(\mathrm{O}(\log K)\) で抑えられるので \(\frac{1}{4!}\) 程度の定数倍がかかります。)

よって、この問題で必要な状態数は \(\mathrm{O}((\log K) ^ 4)\) であるとわかりました。そこで、1.で示した DP を必要な状態の値のみを持って DP することで計算量 \(\mathrm{O}(B (\log K) ^ 4 \log N)\) での DP が可能になります。DPの値の管理は連想配列 ( C++ の std::unordered_map や Python の defaultdict ) を利用すれば容易に行うことが出来ます。

以上よりこの問題を \(B=10\) として \(\mathrm{O}(B (\log K) ^ 4 \log N)\) で解くことが出来ました。AC コードを以下に載せます。

from collections import defaultdict

N, _K = input().split()
K = int(_K)
INF = K + 1

dp = defaultdict(int)
eq_prod = 1

for i in range(len(N)):
  digit = ord(N[i]) - ord('0')
  nxt = defaultdict(int)

  # less -> less
  for prod, val in dp.items():
    for d in range(10):
      nxt_prod = min(INF, prod * d)
      nxt[nxt_prod] += val

  # equal -> less
  for d in range(digit):
    if i == 0 and d == 0:
      continue
    nxt_prod = min(INF, eq_prod * d)
    nxt[nxt_prod] += 1

  # equal -> equal
  eq_prod = min(INF, eq_prod * digit)

  # 1 ... 9
  if i != 0:
    for d in range(1, 10):
      nxt_prod = min(INF, d)
      nxt[nxt_prod] += 1

  dp = nxt

answer = 0

# less
for prod, val in dp.items():
  if prod <= K:
    answer += val

# equal
if eq_prod <= K:
  answer += 1

print(answer)