Hard

题目描述

给你两个正整数 l 和 r。如果一个正整数的各位数字乘积能被各位数字和整除，那么这个数字被称为美丽数字。

返回 l 和 r 之间（包含 l 和 r）美丽数字的数量。

示例 1：

输入：l = 10, r = 20
输出：2
解释：
范围内的美丽数字是 10 和 20。

示例 2：

输入：l = 1, r = 15
输出：10
解释：
范围内的美丽数字是 1, 2, 3, 4, 5, 6, 7, 8, 9, 和 10。

提示：

  • 1 <= l <= r < 10^9
  • 使用数位动态规划。

解题思路

这是一道经典的数位动态规划题目。我们需要统计在 [l, r] 范围内满足"数字乘积能被数字和整除"的数字个数。

核心思路：

  1. 使用数位DP模板，对于每个位置，记录当前的数字和以及数字乘积
  2. 由于乘积和和都可能很大，我们需要进行模运算优化
  3. 关键观察：由于数字和最大为 9×10=90，我们可以用数字和作为模数来压缩状态

状态设计：

  • pos: 当前处理的位置
  • sum: 当前数字和
  • prod_mod: 数字乘积对当前数字和的模值
  • tight: 是否受到上界限制
  • started: 是否已经开始填入非零数字

转移方程： 对于每个位置，我们枚举可能的数字，更新和与乘积，并检查约束条件。

边界处理：

  • 当遇到数字0时，乘积变为0，需要特殊处理
  • 最终判断时检查 prod_mod == 0（即乘积能被和整除）

使用 countBeautiful(r) - countBeautiful(l-1) 的方式计算区间内的美丽数字数量。

代码实现

class Solution {
public:
    int beautifulNumbers(int l, int r) {
        return countBeautiful(r) - countBeautiful(l - 1);
    }
    
private:
    string num;
    int memo[12][100][100][2][2];
    
    int countBeautiful(int x) {
        if (x <= 0) return 0;
        num = to_string(x);
        memset(memo, -1, sizeof(memo));
        return dfs(0, 0, 0, 1, 0);
    }
    
    int dfs(int pos, int sum, int prod_mod, int tight, int started) {
        if (pos == num.length()) {
            if (!started) return 0;
            return sum > 0 && prod_mod == 0 ? 1 : 0;
        }
        
        if (memo[pos][sum][prod_mod][tight][started] != -1) {
            return memo[pos][sum][prod_mod][tight][started];
        }
        
        int limit = tight ? (num[pos] - '0') : 9;
        int result = 0;
        
        for (int digit = 0; digit <= limit; digit++) {
            int new_sum = sum;
            int new_prod_mod = prod_mod;
            int new_tight = tight && (digit == limit);
            int new_started = started;
            
            if (digit > 0 || started) {
                new_sum = sum + digit;
                new_started = 1;
                
                if (digit == 0) {
                    new_prod_mod = 0;
                } else if (new_sum > 0) {
                    new_prod_mod = (prod_mod * digit) % new_sum;
                }
            }
            
            result += dfs(pos + 1, new_sum, new_prod_mod, new_tight, new_started);
        }
        
        return memo[pos][sum][prod_mod][tight][started] = result;
    }
};

class Solution:
    def beautifulNumbers(self, l: int, r: int) -> int:
        def count_beautiful(x):
            if x <= 0:
                return 0
            
            s = str(x)
            n = len(s)
            memo = {}
            
            def dfs(pos, sum_digits, prod_mod, tight, started):
                if pos == n:
                    if not started:
                        return 0
                    return 1 if sum_digits > 0 and prod_mod == 0 else 0
                
                state = (pos, sum_digits, prod_mod, tight, started)
                if state in memo:
                    return memo[state]
                
                limit = int(s[pos]) if tight else 9
                result = 0
                
                for digit in range(limit + 1):
                    new_sum = sum_digits
                    new_prod_mod = prod_mod
                    new_tight = tight and (digit == limit)
                    new_started = started
                    
                    if digit > 0 or started:
                        new_sum = sum_digits + digit
                        new_started = True
                        
                        if digit == 0:
                            new_prod_mod = 0
                        elif new_sum > 0:
                            new_prod_mod = (prod_mod * digit) % new_sum
                    
                    result += dfs(pos + 1, new_sum, new_prod_mod, new_tight, new_started)
                
                memo[state] = result
                return result
            
            return dfs(0, 0, 0, True, False)
        
        return count_beautiful(r) - count_beautiful(l - 1)

public class Solution {
    private string num;
    private int[,,,,] memo;
    
    public int BeautifulNumbers(int l, int r) {
        return CountBeautiful(r) - CountBeautiful(l - 1);
    }
    
    private int CountBeautiful(int x) {
        if (x <= 0) return 0;
        
        num = x.ToString();
        memo = new int[12, 100, 100, 2, 2];
        
        for (int i = 0; i < 12; i++)
            for (int j = 0; j < 100; j++)
                for (int k = 0; k < 100; k++)
                    for (int l = 0; l < 2; l++)
                        for (int m = 0; m < 2; m++)
                            memo[i, j, k, l, m] = -1;
        
        return Dfs(0, 0, 0, 1, 0);
    }
    
    private int Dfs(int pos, int sum, int prodMod, int tight, int started) {
        if (pos == num.Length) {
            if (started == 0) return 0;
            return sum > 0 && prodMod == 0 ? 1 : 0;
        }
        
        if (memo[pos, sum, prodMod, tight, started] != -1) {
            return memo[pos, sum, prodMod, tight, started];
        }
        
        int limit = tight == 1 ? (num[pos] - '0') : 9;
        int result = 0;
        
        for (int digit = 0; digit <= limit; digit++) {
            int newSum = sum;
            int newProdMod = prodMod;
            int newTight = (tight == 1 && digit == limit) ? 1 : 0;
            int newStarted = started;
            
            if (digit > 0 || started == 1) {
                newSum = sum + digit;
                newStarted = 1;
                
                if (digit == 0) {
                    newProdMod = 0;
                } else if (newSum > 0) {
                    newProdMod = (prodMod * digit) % newSum;
                }
            }
            
            result += Dfs(pos + 1, newSum, newProdMod, newTight, newStarted);
        }
        
        return memo[pos, sum, prodMod, tight, started] = result;
    }
}

var beautifulNumbers = function(l, r) {
    const memo = new Map();
    
    function gcd(a, b) {
        return b === 0 ? a : gcd(b, a % b);
    }
    
    function dp(pos, tight, started, product, sum, num) {
        if (pos === num.length) {
            if (!started) return 0;
            return product % sum === 0 ? 1 : 0;
        }
        
        const key = `${pos},${tight},${started},${product},${sum}`;
        if (memo.has(key)) return memo.get(key);
        
        let limit = tight ? parseInt(num[pos]) : 9;
        let result = 0;
        
        for (let digit = 0; digit <= limit; digit++) {
            let newTight = tight && (digit === limit);
            let newStarted = started || (digit > 0);
            let newProduct = newStarted ? (started ? product * digit : digit) : 0;
            let newSum = sum + digit;
            
            if (newStarted && digit === 0) newProduct = 0;
            if (newStarted && newProduct > 3628800) continue;
            
            result += dp(pos + 1, newTight, newStarted, newProduct, newSum, num);
        }
        
        memo.set(key, result);
        return result;
    }
    
    function countBeautiful(n) {
        if (n <= 0) return 0;
        memo.clear();
        return dp(0, true, false, 1, 0, n.toString());
    }
    
    return countBeautiful(r) - countBeautiful(l - 1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(log(r) × 90 × 90)
空间复杂度O(log(r) × 90 × 90)

说明：

  • 时间复杂度：数位DP的状态数为 O(位数 × 数字和 × 乘积模值)，其中位数最多10位，数字和最大90，乘积模值最大90
  • 空间复杂度：记忆化存储的状态空间大小