Count beautiful numbers

impl Solution {
  pub fn beautiful_numbers(l: i32, r: i32) -> i32 {
    (Self::count_upto(r) - Self::count_upto(l - 1)) as i32
  }

  // Digit DP: count beautiful numbers in [1, n].
  // A number is beautiful if product_of_digits % sum_of_digits == 0.
  // Key insight: digit product can only have prime factors {2,3,5,7}.
  // So if product != 0, the sum must be 7-smooth too.
  // State (non-tight, started): (pos, sum, has_zero, c2, c3, c5, c7)
  //   sum: cumulative digit sum (≤81 for ≤9 digits)
  //   has_zero: whether any digit so far is 0 (makes product=0)
  //   c2..c7: prime factor counts in product, capped at the max needed
  //     c2 capped at 6 (max v2 of sum≤81 is v2(64)=6)
  //     c3 capped at 4 (max v3 of sum≤81 is v3(81)=4)
  //     c5 capped at 2 (max v5 of sum≤81 is v5(25)=2)
  //     c7 capped at 2 (max v7 of sum≤81 is v7(49)=2)
  fn count_upto(n: i32) -> i64 {
    if n <= 0 { return 0; }
    let digits: Vec<usize> = {
      let mut v = vec![];
      let mut x = n;
      while x > 0 { v.push((x % 10) as usize); x /= 10; }
      v.reverse();
      v
    };
    // memo[pos][sum][hz][c2][c3][c5][c7] for tight=false, started=true
    // sizes: 9 * 82 * 2 * 7 * 5 * 3 * 3 = 464940
    let mut memo = vec![-1i64; 9 * 82 * 2 * 7 * 5 * 3 * 3];
    Self::dp(0, true, false, 0, false, 0, 0, 0, 0, &digits, &mut memo)
  }

  fn dp(
    pos: usize, tight: bool, started: bool,
    sum: usize, hz: bool,
    c2: usize, c3: usize, c5: usize, c7: usize,
    digits: &[usize], memo: &mut Vec<i64>,
  ) -> i64 {
    if pos == digits.len() {
      return if started && Self::is_beautiful(sum, hz, c2, c3, c5, c7) { 1 } else { 0 };
    }
    let memo_key = if !tight && started {
      let idx = (((((pos * 82 + sum) * 2 + hz as usize) * 7 + c2) * 5 + c3) * 3 + c5) * 3 + c7;
      if memo[idx] >= 0 { return memo[idx]; }
      Some(idx)
    } else {
      None
    };
    let limit = if tight { digits[pos] } else { 9 };
    let mut result = 0i64;
    for d in 0..=limit {
      let new_tight = tight && (d == limit);
      if !(started || d > 0) {
        result += Self::dp(pos + 1, new_tight, false, 0, false, 0, 0, 0, 0, digits, memo);
      } else {
        let new_hz = hz || (d == 0);
        let new_sum = sum + d;
        let (f2, f3, f5, f7) = Self::digit_factors(d);
        result += Self::dp(
          pos + 1, new_tight, true, new_sum, new_hz,
          (c2 + f2).min(6), (c3 + f3).min(4), (c5 + f5).min(2), (c7 + f7).min(2),
          digits, memo,
        );
      }
    }
    if let Some(idx) = memo_key { memo[idx] = result; }
    result
  }

  fn digit_factors(d: usize) -> (usize, usize, usize, usize) {
    match d {
      2 => (1, 0, 0, 0), 3 => (0, 1, 0, 0), 4 => (2, 0, 0, 0),
      5 => (0, 0, 1, 0), 6 => (1, 1, 0, 0), 7 => (0, 0, 0, 1),
      8 => (3, 0, 0, 0), 9 => (0, 2, 0, 0), _ => (0, 0, 0, 0),
    }
  }

  fn is_beautiful(sum: usize, hz: bool, c2: usize, c3: usize, c5: usize, c7: usize) -> bool {
    if sum == 0 { return false; }
    if hz { return true; } // product=0, 0%sum==0
    let mut s = sum;
    let mut n2 = 0usize; while s % 2 == 0 { s /= 2; n2 += 1; }
    let mut n3 = 0usize; while s % 3 == 0 { s /= 3; n3 += 1; }
    let mut n5 = 0usize; while s % 5 == 0 { s /= 5; n5 += 1; }
    let mut n7 = 0usize; while s % 7 == 0 { s /= 7; n7 += 1; }
    s == 1 && c2 >= n2 && c3 >= n3 && c5 >= n5 && c7 >= n7
  }
}