反倍数

题目描述

给定三个整数 a,b,c 如果一个整数既不是 a 的整数倍也不是 bbb 的整数倍还不是 c 的整数倍，则这个数称为反倍数。

请问在 1 至 n 中有多少个反倍数。

输入描述

输入的第一行包含一个整数 n。

第二行包含三个整数 a,b,c 相邻两个数之间用一个空格分隔。

其中，1≤n≤1000000，1≤a≤n，1≤b≤n，1≤c≤n。

输出描述

输出一行包含一个整数，表示答案。

输入输出样例

示例

输入

30
2 3 6

输出

10

样例说明：

以下这些数满足要求：1, 5, 7, 11, 13, 17, 19, 23, 25, 29。

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

来自: 0反倍数 – 蓝桥云课

我的题解

def revserse_multipe_num(n, a, b, c):
    """
    计算在 1 到 n 之间不是 a、b、c 的倍数的数的个数。
    
    参数:
    n: int，计算范围的上限（包含 n）。
    a: int，第一个数。
    b: int，第二个数。
    c: int，第三个数。
    
    返回值:
    int，不是 a、b、c 的倍数的数的个数。
    """
    count = 0  # 计数器，记录满足条件的数的个数
    for i in range(1, n+1):
        # 如果 i 不是 a、b、c 的倍数，则计数器加一
        if i % a != 0 and i % b != 0 and i % c != 0:
            count += 1
    return count


# 从用户输入中获取 n、a、b、c 的值
n = int(input())
a, b, c = map(int, input().split())
# 调用函数并打印结果
print(revserse_multipe_num(n, a, b, c))

AI 题解

只给出创新（不同于我的题解）、优秀的解

ChatGLM-4.0

为了解决这个问题，我们可以采用一种直接的方法：遍历从1到n的所有整数，检查每个数是否同时不是a、b和c的倍数。然而，这种方法在n非常大时效率很低。

一个更高效的方法是使用容斥原理。我们可以先计算从1到n的所有整数中a、b和c的倍数的个数，然后计算a和b、b和c、a和c的公倍数的个数，最后从总数n中减去这些倍数的个数，再加上三个数a、b和c的公倍数的个数（因为它们被减去了两次）。

下面是Python代码实现：

def gcd(a, b):
    # 计算最大公约数
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    # 计算最小公倍数
    return a * b // gcd(a, b)

def count_multiples(n, a, b, c):
    # 计算从1到n的a、b、c的倍数的个数
    count_a = n // a
    count_b = n // b
    count_c = n // c

    # 计算a和b、b和c、a和c的公倍数的个数
    count_ab = n // lcm(a, b)
    count_bc = n // lcm(b, c)
    count_ac = n // lcm(a, c)

    # 计算a、b、c三个数的公倍数的个数
    count_abc = n // lcm(lcm(a, b), c)

    # 使用容斥原理计算反倍数的个数
    total_multiples = count_a + count_b + count_c - count_ab - count_bc - count_ac + count_abc
    return n - total_multiples

# 读取输入
n = int(input().strip())
a, b, c = map(int, input().strip().split())

# 计算并输出结果
print(count_multiples(n, a, b, c))

请注意，这个代码假设输入是通过标准输入提供的，并且我们使用了gcd和lcm函数来计算最大公约数和最小公倍数。这些函数对于计算倍数和公倍数是必要的。

运行上述代码，并使用样例输入，你应该会得到输出结果10，与样例输出一致。

---

存档地址：https://www.yuque.com/worthstudy/study/iagm3q1tchrmggnl?singleDoc# 《反倍数》