反倍数

题目描述

给定三个整数 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))

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

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


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

© 版权声明
THE END
喜欢就点赞支持一下吧,如果觉得不错或日后有所需要,可以收藏文章和关注作者哦。
点赞1打赏 分享
评论 抢沙发

请登录后发表评论

    暂无评论内容