如何用Java实现容斥原理求解指定质数整除计数问题

没问题，我来帮你搞定这个需求。咱们先把问题和思路理清楚，再上代码。

核心思路：容斥原理 #

正如你给出的例子，计算1到M中能被任意一个质数整除的数的个数，核心就是容斥原理：

• 先把每个质数的倍数个数加起来
• 再减去每两个质数乘积的倍数个数（因为这部分被重复计算了）
• 接着加上每三个质数乘积的倍数个数（之前减多了）
• 以此类推，直到处理完所有N个质数的组合：
  • 当子集包含奇数个质数时，加该子集乘积的倍数个数
  • 当子集包含偶数个质数时，减该子集乘积的倍数个数

注意：如果某个子集的乘积大于M，那它的倍数个数就是0，可以直接跳过，不影响结果。

Java实现代码 #

这里我用二进制子集枚举的方式来实现，这种方法直观且高效，适合处理N不太大的情况（如果N超过30，可能会有整数溢出问题，需要用BigInteger，不过质数数量一般不会这么多）：

import java.util.Arrays;

public class InclusionExclusion {
    public static int countDivisibleNumbers(int[] primes, int M) {
        int n = primes.length;
        int count = 0;

        // 遍历所有非空子集：从1到(1<<n)-1
        for (int mask = 1; mask < (1 << n); mask++) {
            int bits = Integer.bitCount(mask); // 统计子集里的质数个数
            long product = 1;
            boolean overflow = false;

            // 计算当前子集的质数乘积
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    // 检查乘积是否溢出，或者超过M（避免无效计算）
                    if (product > M / primes[i]) {
                        overflow = true;
                        break;
                    }
                    product *= primes[i];
                }
            }

            if (overflow) {
                continue; // 乘积超过M，倍数个数为0，跳过
            }

            // 根据子集元素个数的奇偶性，决定加或减
            if (bits % 2 == 1) {
                count += M / product;
            } else {
                count -= M / product;
            }
        }

        return count;
    }

    public static void main(String[] args) {
        // 测试示例：1到500中能被3、5、7整除的数的个数
        int[] primes = {3, 5, 7};
        int M = 500;
        int result = countDivisibleNumbers(primes, M);
        System.out.println("结果：" + result); // 输出应该是271
    }
}

代码说明 #

1. 二进制子集枚举：mask从1到(1<<n)-1，每个mask的二进制位对应是否选中某个质数（比如mask=5是二进制101，表示选中第0和第2个质数）。
2. 乘积溢出检查：在计算质数乘积时，提前判断是否会超过M或者整数溢出，避免错误计算。
3. 奇偶判断：用Integer.bitCount(mask)获取子集里的质数个数，奇数加、偶数减，符合容斥原理的规则。

测试验证 #

手动计算示例：

• P(3)=500/3=166，P(5)=100，P(7)=71 → 总和166+100+71=337
• P(15)=33，P(35)=14，P(21)=23 → 总和33+14+23=70 → 337-70=267
• P(105)=4 → 267+4=271

运行代码后输出的结果正好是271，和手动计算一致，说明代码是正确的。

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