思路: 容斥原理

1. 计算每项活动单独发生的天数：

   • 跑步的天数： $|A| = \lfloor \frac{n}{a} \rfloor$
   • 打球的天数： $|B| = \lfloor \frac{n}{b} \rfloor$
   • 去图书馆的天数： $|C| = \lfloor \frac{n}{c} \rfloor$

2. 计算两两活动同时发生的天数：

   • 跑步和打球同时发生的天数： $|A \cap B| = \lfloor \frac{n}{lcm(a, b)} \rfloor$
   • 跑步和去图书馆同时发生的天数： $|A \cap C| = \lfloor \frac{n}{lcm(a, c)} \rfloor$
   • 打球和去图书馆同时发生的天数： $|B \cap C| = \lfloor \frac{n}{lcm(b, c)} \rfloor$

3. 计算三项活动同时发生的天数： $|A \cap B \cap C|=\lfloor{n/lcm(a, b, c)}\rfloor$

4. 应用容斥原理计算：

   根据容斥原理，至少两项活动发生的天数为：

   $$|A \cap B|+|A \cap C|+|B \cap C|-2|A\cap B\cap C|$$

   这里减去两倍的三项交集，是因为三项交集的天数在两两交集中总共计算了三次，需要减去 2 倍。

5. 另一种理解方法：

   恰好两项活动发生的次数为：

   $$|A \cap B|+|A \cap C|+|B \cap C|-3|A\cap B\cap C|$$

   恰好三项活动发生的次数为:

   $$|A \cap B \cap C|$$

   两项相加就是答案。

代码

java

import java.util.Scanner;

public class Main {
    // 计算最小公倍数
    public static long lcm(long x, long y) {
        return (x * y) / gcd(x, y);
    }

    // 计算最大公约数
    public static long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();  // 读取测试用例的数量
        
        // 遍历每个测试用例
        for (int i = 0; i < T; i++) {
            long n = scanner.nextLong();  // 天数
            long a = scanner.nextLong();  // 跑步的间隔
            long b = scanner.nextLong();  // 打球的间隔
            long c = scanner.nextLong();  // 图书馆的间隔

            // 计算每对活动的最小公倍数
            long lcm_ab = lcm(a, b);
            long lcm_ac = lcm(a, c);
            long lcm_bc = lcm(b, c);
            long lcm_abc = lcm(lcm_ab, c); // 计算 a, b, c 的最小公倍数

            // 计算每对活动发生的次数
            long count_ab = n / lcm_ab;
            long count_ac = n / lcm_ac;
            long count_bc = n / lcm_bc;
            long count_abc = n / lcm_abc;

            // 根据容斥原理计算至少两项活动发生的天数
            long at_least_two = count_ab + count_ac + count_bc - 2 * count_abc;
            
            System.out.println(at_least_two);  // 输出结果
        }

        scanner.close();
    }
}

python

import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

def lcm_three(a, b, c):
    return lcm(lcm(a, b), c)

def main():
    T = int(input())  # 读取测试用例的数量
    results = []
    
    for _ in range(T):
        n, a, b, c = map(int, input().split())  # 逐行读取 n, a, b, c
        
        # 计算每对活动的最小公倍数
        lcm_ab = lcm(a, b)
        lcm_ac = lcm(a, c)
        lcm_bc = lcm(b, c)
        lcm_abc = lcm_three(a, b, c)
        
        # 计算每对活动的天数
        count_ab = n // lcm_ab
        count_ac = n // lcm_ac
        count_bc = n // lcm_bc
        count_abc = n // lcm_abc
        
        # 根据容斥原理计算至少两项活动发生的天数
        at_least_two = count_ab + count_ac + count_bc - 2 * count_abc
        
        results.append(str(at_least_two))  # 收集结果
    
    # 输出所有结果
    print("\n".join(results))

if __name__ == "__main__":
    main()

cpp

#include <iostream>
#include <algorithm>

using namespace std;

// 计算最大公约数
long long gcd(long long a, long long b) {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 计算最小公倍数
long long lcm(long long x, long long y) {
    return (x * y) / gcd(x, y);
}

int main() {
    int T;
    cin >> T;  // 读取测试用例的数量

    // 遍历每个测试用例
    for (int i = 0; i < T; i++) {
        long long n, a, b, c;
        cin >> n >> a >> b >> c;  // 逐行读取 n, a, b, c
        
        // 计算每对活动的最小公倍数
        long long lcm_ab = lcm(a, b);
        long long lcm_ac = lcm(a, c);
        long long lcm_bc = lcm(b, c);
        long long lcm_abc = lcm(lcm_ab, c);  // 计算 a, b, c 的最小公倍数

        // 计算每对活动发生的次数
        long long count_ab = n / lcm_ab;
        long long count_ac = n / lcm_ac;
        long long count_bc = n / lcm_bc;
        long long count_abc = n / lcm_abc;

        // 根据容斥原理计算至少两项活动发生的天数
        long long at_least_two = count_ab + count_ac + count_bc - 2 * count_abc;
        
        cout << at_least_two << endl;  // 输出结果
    }

    return 0;
}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

小红从今天(第$1$天)开始每$a$天(第$a$天、第$a+a$天、……)会去跑步，每$b$天会去打球，每$c$天会去图书馆。

小红想知道从第$1$天到第$n$天中至少需要办两件事的天数。

输入描述

每个测试文件均包含多组测试数。第一行输入一个整数$T$($1≤T≤10^5$)，代表数据组数，每组 测试数据描述如下: 每行输入四个整数$n,a,b,c$($1≤n≤10^9;1≤ a,b, c≤10^4$)，含义如题面所示。

输出描述

对于每一组测试数据，在一行上输出一个整数，代表$n$天中至少需要办两件事的天数。

样例1

输入

2
1 1 1 1
5 1 2 3

输出

1
3

说明

对于第一个样例，第$1$天至少需要办三件事。 对于第二个样例，其中一种解释是，小红会在第$1,2,3,4,5$天去跑步，在第$2,4$天去打球，第 $3$天去图书馆。所以第$2,3,4$天都至少需要办两件事以上。