如何将统计1~d中被k/l/m/n整除数的算法时间复杂度降至O(1)

核心原理 #

使用容斥原理计算1~d范围内能被任意目标数整除的数字总个数，无需遍历1到d的所有数字，运算次数固定，时间复杂度为常数级O(1)。
四个集合的容斥计算公式如下：

符合条件的总数量 = 单个数字的倍数总数 - 任意两个数字公倍数的倍数总数 + 任意三个数字公倍数的倍数总数 - 四个数字公倍数的倍数总数
其中每个类别的数量直接用d / 对应最小公倍数即可得到（Java整数除法默认向下取整，刚好符合需求）。

依赖基础工具方法 #

需要先实现两个基础运算：

• 最大公约数（GCD）：采用欧几里得算法快速计算
• 最小公倍数（LCM）：LCM(a,b) = a * b / GCD(a,b)，注意先做除法再做乘法，避免整数溢出

完整代码实现 #

import java.util.Scanner;

public class CountDivisible {
    // 计算最大公约数
    private static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    // 计算最小公倍数
    private static int lcm(int a, int b) {
        if (a == 0 || b == 0) return 0;
        return a / gcd(a, b) * b;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int k = in.nextInt();
        int l = in.nextInt();
        int m = in.nextInt();
        int n = in.nextInt();
        int d = in.nextInt();

        // 单个数的倍数总数
        long s1 = (long) d / k + d / l + d / m + d / n;
        // 任意两个数公倍数的倍数总数
        long s2 = (long) d / lcm(k, l) + d / lcm(k, m) + d / lcm(k, n)
                + d / lcm(l, m) + d / lcm(l, n) + d / lcm(m, n);
        // 任意三个数公倍数的倍数总数
        long s3 = (long) d / lcm(lcm(k, l), m) + d / lcm(lcm(k, l), n)
                + d / lcm(lcm(k, m), n) + d / lcm(lcm(l, m), n);
        // 四个数公倍数的倍数总数
        long s4 = (long) d / lcm(lcm(lcm(k, l), m), n);

        long sum = s1 - s2 + s3 - s4;
        System.out.println(sum);
    }
}

方案优势 #

• 完全不需要循环遍历，运算次数和d的大小完全无关，即便d取1e9甚至更大的数值也能瞬间得到结果
• 结果和遍历方案完全一致，容斥原理天然解决了重复统计的问题

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