写在前面

全世界人的编程水平下降一万倍，只有我的水平保持不变！今天刷题刷上头了，又双叒叕看见一道难题小C的数字倍数问题，是公倍数公约数还是互质？点开定睛一看，居然是难度极高，史上无人能解的倍数难题，这一刻，全世界都炸了锅：”什么？！他居然点开了数字倍数问题，这道题里无比繁杂的数学方法全世界能够掌握的人都寥寥无几！”

问题描述

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

测试样例

样例1：

输入：a = 2,b = 3,c = 4,l = 1,r = 10
输出：7

样例2：

输入：a = 5,b = 7,c = 11,l = 15,r = 100
输出：34

样例3：

输入：a = 1,b = 1,c = 1,l = 1,r = 1000
输出：1000

解题思路

看着这道对世人无比复杂的难题，在一片惊呼声中，我打开了侧边栏的MarsCode AI，向他问道：“给我一点思路提示。””是MarsCode AI！早已失传的头部大厂的高科技！他居然能直接在浏览器里命令它，这学生是什么来头？！”只见AI迅速地作出了判断：

好的，让我们来分析一下这个问题。

问题理解

你需要计算在区间 [l, r] 内，有多少个数是 a 的倍数，或者是 b 的倍数，或者是 c 的倍数。

数据结构选择

这个问题不需要复杂的数据结构，只需要基本的整数运算。

算法步骤

  1. 遍历区间：从 l 到 r 遍历每一个数。
  2. 检查倍数：对于每一个数，检查它是否是 a、b 或 c 的倍数。
  3. 计数：如果满足条件，则计数器加一。

优化思路

  1. 直接计算倍数：可以通过直接计算在区间 [l, r] 内 a、b、c 的倍数的个数，然后使用容斥原理来避免重复计数。
  2. 容斥原理：计算 a、b、c 的倍数的个数，然后减去 a 和 b、a 和 c、b 和 c 的公倍数的个数，再加上 a、b、c 的公倍数的个数。

总结

你可以选择直接遍历区间并检查每个数是否是 a、b 或 c 的倍数，或者使用容斥原理来优化计算过程。

希望这些思路对你有帮助！如果你有更多问题，欢迎继续提问。

题解

看见AI的回答后，我的嘴角扬起一抹自信：“哼哼，其实我早就看出解法了，只是验证一下这AI的智商咋样。” 随即我开始劈里啪啦地敲下键盘，一个个英文字符在我的指尖跳动。“难以置信，他的代码能力已经是世界顶级了！”经验丰富的教授大牛也露出了颓然的神情。不到一小时，我就完成了这道难题，刹那间，沧海桑田，黄粱一梦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int solution(int a, int b, int c, int l, int r) {
    int ans {};
    for (int i {l}; i <= r; ++i)
    {
        if (i % a == 0 || i % b == 0 || i % c == 0)
            ans++;
    }
    return ans;
}

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

后记

我在算法课上惊醒，身边的教授无奈地望着我惺忪的睡眼：“说出一个时间复杂度为nlogn的排序算法。” 我信心满满地回答道：“那当然是冒泡排序。”