思路: 容斥原理

计算每项活动单独发生的天数：
- 跑步的天数： $|A| = \lfloor \frac{n}{a} \rfloor$
- 打球的天数： $|B| = \lfloor \frac{n}{b} \rfloor$
- 去图书馆的天数： $|C| = \lfloor \frac{n}{c} \rfloor$
计算两两活动同时发生的天数：
- 跑步和打球同时发生的天数： $|A \cap B| = \lfloor \frac{n}{lcm(a, b)} \rfloor$

P2147.2024.9.29-第3题-小红办事

1000ms

Difficulty: 5

所属公司 : 字节

算法与标签>数学

小红从今天(第 $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$ 天中至少需要办两件事的天数。

输入

2
1 1 1 1
5 1 2 3

输出

1
3

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

编辑器加载中…

输入

预期输出（选填）