统计[L,R]区间内满足数值比等于数位乘积比的无序整数对数量

问题要求 #

给定两个整数L和R，统计区间[L, R]内符合要求的无序整数对(A, B)的总数量，判断条件为：A与B的比值等于A的数位乘积与B的数位乘积的比值。

条件等价转换 #

原判断条件可交叉相乘化简，注意排除数位含0的无效数字（数位乘积为0，无合法比值）：

原始条件：$\frac{A}{B} = \frac{prod(A)}{prod(B)}$，其中$prod(X)$为$X$所有数位的乘积
等价条件：$\frac{A}{prod(A)} = \frac{B}{prod(B)}$，仅适用于$prod(A)、prod(B)$均不为0的数字

实现思路 #

• 遍历区间内所有数字，过滤掉数位含0、数位乘积为0的无效数字
• 对每个有效数字，计算X/prod(X)约分后的分子分母元组作为唯一标识，统计每个标识的出现次数
• 对每个标识的出现次数$k$，计算可组成的无序对数量$C(k,2) = \frac{k*(k-1)}{2}$，求和得到最终结果

示例代码（Python） #

import math
from collections import defaultdict

def get_digit_prod(num: int) -> int:
    prod = 1
    while num:
        digit = num % 10
        if digit == 0:
            return 0
        prod *= digit
        num = num // 10
    return prod

def count_valid_pairs(L: int, R: int) -> int:
    count_map = defaultdict(int)
    for num in range(L, R + 1):
        prod = get_digit_prod(num)
        if prod == 0:
            continue
        # 约分后用元组做key避免浮点数精度问题
        gcd_val = math.gcd(num, prod)
        key = (num // gcd_val, prod // gcd_val)
        count_map[key] += 1
    res = 0
    for cnt in count_map.values():
        res += cnt * (cnt - 1) // 2
    return res

内容的提问来源于stack exchange，提问作者user16967671