数字倍数问题

问题描述

小U对数字倍数问题很感兴趣，她想知道在区间 $[l, r]$ 内，有多少个数是 $a$ 的倍数，或者是 $b$ 的倍数，或者是 $c$ 的倍数。你需要帮小U计算出这些数的个数。

解题思路

本题要求统计区间内能被给定的多个数中的至少一个整除的整数个数，是典型的容斥原理应用。

容斥原理

容斥原理用于计算多个集合的并集的基数，其公式为：

对于三个集合，有：

应用到解题

  • 集合定义： 令 $A$、$B$、$C$ 分别表示能被 $a$、$b$、$c$ 整除的整数集合。
  • 目标： 计算 $|A \cup B \cup C|$，即在区间内能被 $a$、$b$ 或 $c$ 整除的整数个数。

计算步骤

  1. 计算单个集合的基数： 计算能被 $a$、$b$、$c$ 整除的整数个数，分别记为 $N_a$、$N_b$、$N_c$。
  2. 计算集合的交集的基数：
    • $N_{ab}$：能同时被 $a$ 和 $b$ 整除的整数个数。
    • $N_{ac}$：能同时被 $a$ 和 $c$ 整除的整数个数。
    • $N_{bc}$：能同时被 $b$ 和 $c$ 整除的整数个数。
  3. 计算三个集合的交集的基数：
    • $N_{abc}$：能同时被 $a$、$b$、$c$ 整除的整数个数。
  4. 应用容斥原理：
    • 求和公式：

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

long long lcm(int a, int b)
{
    return (long long)a / gcd(a, b) * b;
}

int countDiv(int l, int r, long long k)
{
    return r / k - (l - 1) / k;
}

int solution(int a, int b, int c, int l, int r)
{
    long long ab = lcm(a, b);
    long long ac = lcm(a, c);
    long long bc = lcm(b, c);
    long long abc = lcm(ab, c);

    int Na = countDiv(l, r, a);
    int Nb = countDiv(l, r, b);
    int Nc = countDiv(l, r, c);
    int Nab = countDiv(l, r, ab);
    int Nac = countDiv(l, r, ac);
    int Nbc = countDiv(l, r, bc);
    int Nabc = countDiv(l, r, abc);

    return Na + Nb + Nc - Nab - Nac - Nbc + Nabc;
}

int main()
{
    cout << (solution(2, 3, 4, 1, 10) == 7) << endl;
    cout << (solution(5, 7, 11, 15, 100) == 34) << endl;
    cout << (solution(1, 1, 1, 1, 1000) == 1000) << endl;
    
    return 0;
}

代码解析

  • gcd 函数： 计算两个数的最大公约数，使用辗转相除法（欧几里得算法）。
  • lcm 函数： 计算两个数的最小公倍数，公式为：
  • countDiv 函数： 计算区间 $[l, r]$ 内能被 $k$ 整除的整数个数，公式为：
  • solution 函数：
  1. 计算最小公倍数：
    • 计算 $a$、$b$、$c$ 两两之间的最小公倍数：ab 、 ac 、 bc 。
    • 计算三个数的最小公倍数： abc 。
  2. 计算各个集合的基数：
    • 使用 countDiv 函数计算能被 $a$、$b$、$c$、 ab 、 ac 、 bc 、 abc 整除的整数个数。
  3. 应用容斥原理：
    • 按照公式返回结果。

知识点总结

  • 最大公约数（GCD）： 求两个整数的最大公约数是数论中的基本算法，可使用辗转相除法实现。
  • 最小公倍数（LCM）： 两个数的最小公倍数等于它们的乘积除以最大公约数。
  • 容斥原理： 用于解决多个集合并集的基数问题，是组合数学中的重要原理。

时间复杂度

  • GCD 和 LCM 计算： 每次计算的时间复杂度为 $O(\log \min(a, b))$。
  • 总体复杂度： 因为涉及常数次的 GCD、LCM 和简单的整数计算，故总体时间复杂度为 $O(\log \min(a, b, c))$。

总结

本题通过 容斥原理 解决在区间内统计能被多个数中的至少一个整除的整数个数的问题，并应用最小公倍数和最大公约数的算法求解。