Official

E - 桁の積 / Product of Digits Editorial by admin

GPT 5.2 High

Overview

Among the integers in the interval \([L,R]\), we count how many have a “product of digits in decimal representation” \(f(n)\) exactly equal to \(K\). Since \(R\le 10^{18}\) is extremely large, we use digit DP instead of brute force enumeration.

Analysis

Key Observation 1: When \(K>0\), the only usable prime factors are \(2,3,5,7\)

Each digit is \(1\)–\(9\) (digit \(0\) makes the product \(0\), so it’s forbidden when \(K>0\)), and
the prime factors of \(1..9\) are only \(2,3,5,7\). For example: - \(8=2^3\) - \(9=3^2\) - \(6=2\cdot 3\) - \(5=5\)

Therefore, if we factorize \(K\) and any prime factor other than \(2,3,5,7\) remains (e.g., \(K\) contains \(11\)), it is impossible to construct, so the answer is \(0\).
In the code, factorize_k divides out \(2,3,5,7\) from \(K\), and if the remainder is not \(1\), it is determined to be impossible.

Key Observation 2: \(K=0\) is easily handled separately

\(f(n)=0\) happens if and only if “the number contains the digit \(0\) somewhere.”
Therefore: - From the total count of numbers in the interval \((R-L+1)\), - Subtract the count of “numbers that do not contain 0.”

This “count of numbers not containing 0” can also be computed with digit DP counting up to \([1,n]\) (count_nozero_leq).

Why a naive approach doesn’t work

Since \(R\) can be up to \(10^{18}\), the interval length can be up to \(10^{18}\) numbers. Computing the digit product for each \(n\) and checking is obviously too slow.
Instead, we use digit DP to count “the number of values \(\le n\) satisfying the condition,” and compute the interval using differences.

Algorithm

1. Preprocessing: Create the \((2,3,5,7)\) exponent tuple for each digit \(d(0..9)\)

Factorize each digit \(d\): [ d = 2^{e2}\cdot 3^{e3}\cdot 5^{e5}\cdot 7^{e7} ] and store \((e2,e3,e5,e7)\) in DIG_FACT[d]. Examples: - DIG_FACT[8]=(3,0,0,0) - DIG_FACT[6]=(1,1,0,0) - DIG_FACT[1]=(0,0,0,0)

2. Case \(K=0\)

count_nozero_leq(n): Count numbers \(1\le x\le n\) that “do not use 0 after the number has started” using digit DP. - State: pos (how many digits have been processed), started (whether we are still in the leading zeros), tight (whether we are still matching the upper bound) - Transition: When still not started (started=0), choosing 0 is allowed (it just advances the position without starting the number). Once started, 0 is forbidden.

The count of “numbers not containing 0” in the interval \([L,R]\) is
count_nozero_leq(R) - count_nozero_leq(L-1),
so the desired answer is [ (R-L+1) - \text{nozero} ]

3. Case \(K>0\): Digit DP managing remaining exponents

First, decompose \(K\) as [ K=2^{t2}\cdot 3^{t3}\cdot 5^{t5}\cdot 7^{t7} ] If there are other factors remaining, it is impossible (answer is \(0\)).

Then count_prod_leq(n, (t2,t3,t5,t7)) counts numbers \(1\le x\le n\) with \(f(x)=K\).

DP States

Define dfs(pos, e2, e3, e5, e7, started, tight) as: - We have decided digits up to position pos from the top - The remaining required exponents are \((e2,e3,e5,e7)\) - started: whether we are still in the leading zeros portion - tight: whether we still match the upper bound \(n\) up to this point

Transitions

  • If started=0 and we choose d=0: the number hasn’t started yet, so we don’t reduce exponents (treated as leading zero).
  • Otherwise, d=0 is forbidden (since \(K>0\), the product would become 0).
  • When placing d=1..9, we consume exponents by DIG_FACT[d]=(a2,a3,a5,a7).
    • If all conditions like a2<=e2 are satisfied, proceed to the next state (subtract remaining exponents).
    • If not satisfied, this digit cannot be chosen (it would cause the product to exceed \(K\) or introduce a different factor).

Terminal Condition

When all digits have been processed (pos==len): - If the number has properly started (started=1) - And all remaining exponents are \(0\)

then count it as 1; otherwise 0.

Finally, the interval is computed with the usual difference: [ \text{count}(L..R)=\text{count}(\le R)-\text{count}(\le L-1) ]

Complexity

Let \(D=\text{number of digits}\le 19\), and \(K=2^{t2}3^{t3}5^{t5}7^{t7}\):

  • Time complexity:
    • When \(K=0\): approximately \(O(D\cdot 10 \cdot 2 \cdot 2)\) (standard digit DP)
    • When \(K>0\): approximately
      [ O\bigl(D\cdot (t2+1)(t3+1)(t5+1)(t7+1)\cdot 10\bigr) ] (including tight/started as constant factors)
  • Space complexity:
    • Proportional to the number of memoized DP states: [ O\bigl(D\cdot (t2+1)(t3+1)(t5+1)(t7+1)\bigr) ]

※ Since \(K\le 10^{18}\), each of \(t2,t3,t5,t7\) is at most a few dozen, which stays within a practical size.

Implementation Notes

  • Handling \(K=0\) separately makes things simple and fast (subtract “numbers not containing 0”).

  • When \(K>0\), digit 0 is always forbidden (except for leading zeros). Forgetting this leads to wrong answers.

  • Maintain started to properly handle leading zero sequences where the number hasn’t started yet (don’t count the case where started=0 at the end, as no actual number exists).

  • Use lru_cache for memoization to avoid recomputing the same states.

  • If \(K\) has any prime factor other than \(2,3,5,7\) remaining, immediately output 0 (since it cannot be formed as a product of digits).

    Source Code

import sys
from functools import lru_cache

DIG_FACT = [(0, 0, 0, 0)] * 10
tmp = []
for d in range(10):
    x = d
    e2 = e3 = e5 = e7 = 0
    while x > 0 and x % 2 == 0:
        x //= 2
        e2 += 1
    while x > 0 and x % 3 == 0:
        x //= 3
        e3 += 1
    while x > 0 and x % 5 == 0:
        x //= 5
        e5 += 1
    while x > 0 and x % 7 == 0:
        x //= 7
        e7 += 1
    tmp.append((e2, e3, e5, e7))
DIG_FACT = tmp


def factorize_k(k: int):
    e2 = e3 = e5 = e7 = 0
    while k % 2 == 0:
        k //= 2
        e2 += 1
    while k % 3 == 0:
        k //= 3
        e3 += 1
    while k % 5 == 0:
        k //= 5
        e5 += 1
    while k % 7 == 0:
        k //= 7
        e7 += 1
    return (e2, e3, e5, e7), k


def count_nozero_leq(n: int) -> int:
    if n <= 0:
        return 0
    digits = list(map(int, str(n)))
    m = len(digits)

    @lru_cache(None)
    def dfs(pos: int, started: int, tight: int) -> int:
        if pos == m:
            return 1 if started else 0
        lim = digits[pos] if tight else 9
        res = 0
        for d in range(lim + 1):
            nt = 1 if (tight and d == lim) else 0
            if not started and d == 0:
                res += dfs(pos + 1, 0, nt)
            else:
                if d == 0:
                    continue
                res += dfs(pos + 1, 1, nt)
        return res

    return dfs(0, 0, 1)


def count_prod_leq(n: int, target_exps) -> int:
    if n <= 0:
        return 0
    digits = list(map(int, str(n)))
    m = len(digits)
    t2, t3, t5, t7 = target_exps

    @lru_cache(None)
    def dfs(pos: int, e2: int, e3: int, e5: int, e7: int, started: int, tight: int) -> int:
        if pos == m:
            return 1 if started and e2 == 0 and e3 == 0 and e5 == 0 and e7 == 0 else 0
        lim = digits[pos] if tight else 9
        res = 0
        for d in range(lim + 1):
            nt = 1 if (tight and d == lim) else 0
            if not started and d == 0:
                res += dfs(pos + 1, e2, e3, e5, e7, 0, nt)
            else:
                if d == 0:
                    continue
                a2, a3, a5, a7 = DIG_FACT[d]
                if a2 <= e2 and a3 <= e3 and a5 <= e5 and a7 <= e7:
                    res += dfs(pos + 1, e2 - a2, e3 - a3, e5 - a5, e7 - a7, 1, nt)
        return res

    return dfs(0, t2, t3, t5, t7, 0, 1)


def main():
    L, R, K = map(int, sys.stdin.readline().split())

    if K == 0:
        nozero = count_nozero_leq(R) - count_nozero_leq(L - 1)
        ans = (R - L + 1) - nozero
        print(ans)
        return

    target_exps, rem = factorize_k(K)
    if rem != 1:
        print(0)
        return

    ans = count_prod_leq(R, target_exps) - count_prod_leq(L - 1, target_exps)
    print(ans)


if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.

posted:
last update: