我懂你现在的痛点——用HashSet存所有倍数再统计大小的思路，在小数据量下确实简单直接，但一旦遇到大规模输入（比如区间范围是1到1e18，或者数字个数很多），不管是遍历倍数的时间开销，还是集合占用的空间，都会直接拉胯。

其实这个问题本质是计算多个集合的并集大小：我们要找的是[start, end]中，属于「n₁的倍数」「n₂的倍数」…「nₙ的倍数」中任意一个的元素总数。正确的打开方式是用容斥原理，不用枚举每个元素，靠数学推导直接算出结果，效率会高得多。

容斥原理的核心思路 #

1. 单个数字的倍数计数：对于数字k，区间[start, end]内k的倍数个数公式是：
   floor(end/k) - floor((start-1)/k)
   这个很好理解：floor(end/k)是1到end中k的倍数总数，减去1到start-1中k的倍数总数，剩下的就是start到end里的数量。

2. 多集合的交集与并集：

   • 两个数字a和b的交集，就是能同时被a和b整除的数，也就是能被它们的**最小公倍数（LCM）**整除的数，同样用上面的公式计算个数。
   • 容斥的规则是：先把所有单个集合的大小加起来，再减去所有两两交集的大小，加上所有三三交集的大小，以此类推——子集元素个数为奇数时加，偶数时减。

用示例验证一下 #

拿你给的例子：start=1，end=10，数字是6、3、7

1. 先算单个集合的大小：

   • 3的倍数：10//3 - 0//3 = 3 - 0 = 3
   • 6的倍数：10//6 - 0//6 = 1 - 0 = 1
   • 7的倍数：10//7 - 0//7 = 1 - 0 = 1
     累加后总和是3+1+1=5

2. 再算两两交集的大小（要减去这些值）：

   • LCM(3,6)=6，倍数个数是1 → 减去1
   • LCM(3,7)=21，10以内没有倍数 → 减去0
   • LCM(6,7)=42，10以内没有倍数 → 减去0
     现在总和变成5 - (1+0+0) = 4

3. 最后算三个数字的交集：LCM(3,6,7)=42，10以内没有倍数 → 加上0
   最终结果就是4，和示例输出完全一致。

代码实现（Python） #

这里给一个可以直接用的实现，还做了一些优化（比如去重输入数字、剪枝超过区间的LCM）：

import math
from itertools import combinations

def count_unique_multiples(start, end, nums):
    # 先去重输入的数字，重复的数字不影响结果
    unique_nums = list(set(nums))
    total = 0
    subset_count = len(unique_nums)
    
    # 遍历所有非空子集
    for subset_size in range(1, subset_count + 1):
        # 生成所有size为subset_size的数字组合
        for combo in combinations(unique_nums, subset_size):
            # 计算当前组合的最小公倍数
            current_lcm = 1
            for num in combo:
                current_lcm = current_lcm * num // math.gcd(current_lcm, num)
                # 如果LCM已经超过end，直接终止计算这个组合
                if current_lcm > end:
                    break
            if current_lcm > end:
                continue
            # 计算该LCM在区间内的倍数个数
            cnt = end // current_lcm - (start - 1) // current_lcm
            # 根据子集大小的奇偶性决定加还是减
            if subset_size % 2 == 1:
                total += cnt
            else:
                total -= cnt
    return total

# 测试你的示例
print(count_unique_multiples(1, 10, [6, 3, 7]))  # 输出4

为什么这个方法更适合大规模输入？ #

• 不需要遍历所有倍数，完全靠数学计算，时间复杂度是O(2^N)（N是去重后的数字个数），只要N不是特别大（比如N≤20），这个效率秒杀HashSet方法。
• 空间开销极小，不需要存储任何倍数，只需要处理子集组合和计算LCM。
• 即使区间范围是1到1e18，这个方法也能瞬间算出结果，因为都是整数运算，没有遍历的开销。

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