基于容斥原理计算倍数的编程任务及数学原理疑问

Hey there! Let's break down how to apply the inclusion-exclusion principle to your problem—once you walk through it with concrete examples, it'll click a lot easier.

We need to count how many numbers in the range [1, b] are divisible by at least one number from the range [2, a]. Your example (a=3, b=30) gives 20 valid numbers, which we'll use to walk through the math step by step.

At its core, inclusion-exclusion fixes the problem of double-counting (or triple-counting, etc.) elements that belong to multiple sets. For your problem:

• Each number y in [2,a] defines a set S_y: all multiples of y in [1,b].
• We want the size of the union of all these sets (since a number just needs to be in at least one S_y to count).
• Without inclusion-exclusion, adding up the sizes of each S_y would count numbers like 6 (divisible by 2 and 3) twice—so we subtract the overlaps, then add back in overlaps we subtracted too many times, and so on.

Let's apply the principle directly to your test case:

1. Calculate individual set sizes #

First, find how many numbers in [1,30] are divisible by each y in [2,3]:

• For y=2: floor(30/2) = 15 numbers (2,4,6,...,30)
• For y=3: floor(30/3) = 10 numbers (3,6,9,...,30)

2. Subtract the size of overlapping sets #

Now, numbers divisible by both 2 and 3 are divisible by their least common multiple (LCM(2,3)=6). We've counted these twice, so we subtract them once:

• Size of overlap: floor(30/6) = 5 numbers (6,12,...,30)

3. Sum it up (no larger overlaps here!) #

Since we only have two sets, there are no triple overlaps to add back. The total count is:
15 + 10 - 5 = 20
Which matches your example perfectly!

When a is bigger (like a=4, b=30), the process extends to account for more sets and overlaps:

1. List all non-empty subsets of [2,a] #

For a=4, subsets are:

• Size 1: {2}, {3}, {4}
• Size 2: {2,3}, {2,4}, {3,4}
• Size 3: {2,3,4}

2. Calculate LCM for each subset #

• Size 1: LCM(2)=2, LCM(3)=3, LCM(4)=4
• Size 2: LCM(2,3)=6, LCM(2,4)=4, LCM(3,4)=12
• Size 3: LCM(2,3,4)=12

3. Apply inclusion-exclusion rules #

• For subsets of odd size (1,3), add the count of multiples of their LCM
• For subsets of even size (2), subtract the count of multiples of their LCM

Calculations:

• Add: floor(30/2) + floor(30/3) + floor(30/4) + floor(30/12) = 15 + 10 +7 +2 = 34
• Subtract: floor(30/6) + floor(30/4) + floor(30/12) =5 +7 +2=14
• Total: 34 -14 =20 (which makes sense—all multiples of 4 are already multiples of 2, so they don't add new numbers to the count!)

• Start small: Practice with a=2, a=3 first to get comfortable with the pattern.
• LCM is your friend: The overlap of k sets is always the numbers divisible by the LCM of those k numbers.
• Follow the parity rule: Odd-sized subsets add their count, even-sized subsets subtract it.
• Skip subsets where LCM > b: If the LCM of a subset is larger than b, there are 0 multiples in [1,b], so you can ignore that subset entirely.

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