三座灯塔在第 0 秒一起闪了一次，之后第一座灯塔每 a 秒闪一次，第二座每 b 秒闪一次，第三座每 c 秒闪一次。
也就是说，第一座灯塔在第 a 秒、2a 秒、3a 秒、… 闪烁，第二座和第三座同理。
在第 1 秒到第 T 秒（包含第 1 秒和第 T 秒）的整数秒中，求下面三种时刻各有多少个。
第一种，三座灯塔中恰好只有一座闪烁的时刻。
第二种，恰好有两座一起闪烁的时刻。
第三种，三座全部一起闪烁的时刻。
第 0 秒不计入。
周期相同的灯塔也算作不同的灯塔（a = b 时第一座和第二座总是一起闪烁）。
给出 q 个询问，对每个询问按上面的顺序在一行输出三个数，用一个空格隔开。
2 4 6 9 36 2 2 5 9
10 3 1 1 4 0
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
T 最大到 10^15，不可能一秒一秒地数。
周期为 a 的灯塔在 T 秒内闪烁 T 除以 a 的商 次，两座灯塔一起闪烁的时刻每隔两个周期的最小公倍数出现一次。
最小公倍数是 a ÷ 最大公约数(a, b) × b。
最大公约数有 Python math.gcd、C++ std::gcd（<numeric>），其他语言要自己写一个用 while (y != 0) 反复取余数的函数。
Python 用 math.lcm(a, b, c) 可以一次求出三个数的最小公倍数。
陷阱一：把两个周期的乘积当作共同周期是错的。
4 秒和 6 秒每 12 秒相遇一次，而不是 24 秒。
陷阱二：两座灯塔重叠的次数里也包含三座全部重叠的时刻。
示例的第一个询问中两两重叠的次数是 3 + 1 + 2 = 6，但第 36 秒在三对中都出现，所以“只有两座”是 6 − 3 × 1 = 3 次。
陷阱三：周期能放进 int，但最小公倍数可以大到 10^18。
在 Java、C#、C、C++ 中用 int 求最小公倍数会溢出（要用 long、long long）。
陷阱四：三个数的最小公倍数可以达到 10^27，连 long 也放不下。
Java、C# 的 long 溢出时不报错而是数值回绕，有时会变成比 T 还小的无关的数；在 C、C++ 中则是未定义行为。
所以在相乘之前先用除法判断是否 part > T / y，超过 T 就不相乘，按“0 次”处理。
Python 的整数没有大小限制，直接相乘即可。
JavaScript、TypeScript 的 number 和 Craykon 的数只在 2^53（约 9 × 10^15）以内精确，但溢出时不会回绕，而是保持为很大的数。
不超过 T 的值都是精确的，所以可以先相乘再用 l > T 比较。
商用 JavaScript Math.floor(t / l)、Craykon 数学.商(t, l) 求。
import mathimport sys def main(): data = sys.stdin.read().split() q = int(data[0]) out = [] for i in range(q): a, b, c, t = map(int, data[1 + 4 * i: 5 + 4 * i]) # 주기마다, 그리고 함께 깜빡이는 주기(최소공배수)마다 T초 안에 몇 번인지 센다 na, nb, nc = t // a, t // b, t // c nab = t // math.lcm(a, b) nac = t // math.lcm(a, c) nbc = t // math.lcm(b, c) nabc = t // math.lcm(a, b, c) # Python의 정수는 넘치지 않는다 # 한 등대만: 그 등대의 횟수에서 다른 등대와 겹친 것을 빼고, 두 번 뺀 '셋 모두'를 한 번 돌려준다 one = (na - nab - nac + nabc) + (nb - nab - nbc + nabc) + (nc - nac - nbc + nabc) # 둘만: 두 등대가 겹친 순간에는 셋이 모두 겹친 순간도 들어 있다 two = (nab - nabc) + (nac - nabc) + (nbc - nabc) out.append(f"{one} {two} {nabc}") print("\n".join(out)) main()const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number); function gcd(x, y) { while (y !== 0) [x, y] = [y, x % y]; return x;} // 최소공배수. cap을 넘으면 cap + 1을 돌려준다("T초 안에는 한 번도 없다"는 뜻)// Number는 넘쳐도 뒤집히지 않고 큰 수로 남으니, 곱한 다음에 견줘도 된다function lcm(x, y, cap) { const l = (x / gcd(x, y)) * y; return l > cap ? cap + 1 : l;} const q = data[0];const out = [];for (let i = 0; i < q; i++) { const [a, b, c, t] = data.slice(1 + 4 * i, 5 + 4 * i); const times = (period) => Math.floor(t / period); // T초 안에 몇 번 const ab = lcm(a, b, t); const na = times(a), nb = times(b), nc = times(c); const nab = times(ab), nac = times(lcm(a, c, t)), nbc = times(lcm(b, c, t)); const nabc = times(lcm(ab, c, t)); // 한 등대만: 그 등대의 횟수에서 다른 등대와 겹친 것을 빼고, 두 번 뺀 '셋 모두'를 한 번 돌려준다 const one = (na - nab - nac + nabc) + (nb - nab - nbc + nabc) + (nc - nac - nbc + nabc); // 둘만: 두 등대가 겹친 순간에는 셋이 모두 겹친 순간도 들어 있다 const two = (nab - nabc) + (nac - nabc) + (nbc - nabc); out.push(`${one} ${two} ${nabc}`);}console.log(out.join("\n"));import { readFileSync } from "node:fs"; const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number); function gcd(x: number, y: number): number { while (y !== 0) [x, y] = [y, x % y]; return x;} // 최소공배수. cap을 넘으면 cap + 1을 돌려준다("T초 안에는 한 번도 없다"는 뜻)// number는 넘쳐도 뒤집히지 않고 큰 수로 남으니, 곱한 다음에 견줘도 된다function lcm(x: number, y: number, cap: number): number { const l = (x / gcd(x, y)) * y; return l > cap ? cap + 1 : l;} const q: number = data[0];const out: string[] = [];for (let i = 0; i < q; i++) { const [a, b, c, t] = data.slice(1 + 4 * i, 5 + 4 * i); const times = (period: number): number => Math.floor(t / period); // T초 안에 몇 번 const ab = lcm(a, b, t); const na = times(a), nb = times(b), nc = times(c); const nab = times(ab), nac = times(lcm(a, c, t)), nbc = times(lcm(b, c, t)); const nabc = times(lcm(ab, c, t)); // 한 등대만: 그 등대의 횟수에서 다른 등대와 겹친 것을 빼고, 두 번 뺀 '셋 모두'를 한 번 돌려준다 const one = (na - nab - nac + nabc) + (nb - nab - nbc + nabc) + (nc - nac - nbc + nabc); // 둘만: 두 등대가 겹친 순간에는 셋이 모두 겹친 순간도 들어 있다 const two = (nab - nabc) + (nac - nabc) + (nbc - nabc); out.push(`${one} ${two} ${nabc}`);}console.log(out.join("\n"));import java.io.*;import java.util.*; public class Main { static long gcd(long x, long y) { while (y != 0) { long r = x % y; x = y; y = r; } return x; } // 최소공배수. cap을 넘으면 cap + 1을 돌려준다("T초 안에는 한 번도 없다"는 뜻) static long lcm(long x, long y, long cap) { long part = x / gcd(x, y); // part * y가 cap보다 큰지를 곱하기 전에 나눗셈으로 묻는다: 곱하면 long도 넘친다 if (part > cap / y) return cap + 1; return part * y; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int q = Integer.parseInt(br.readLine().trim()); StringBuilder sb = new StringBuilder(); for (int i = 0; i < q; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); long a = Long.parseLong(st.nextToken()); long b = Long.parseLong(st.nextToken()); long c = Long.parseLong(st.nextToken()); long t = Long.parseLong(st.nextToken()); long ab = lcm(a, b, t); long na = t / a, nb = t / b, nc = t / c; long nab = t / ab, nac = t / lcm(a, c, t), nbc = t / lcm(b, c, t); long nabc = t / lcm(ab, c, t); // 한 등대만: 그 등대의 횟수에서 다른 등대와 겹친 것을 빼고, 두 번 뺀 '셋 모두'를 한 번 돌려준다 long one = (na - nab - nac + nabc) + (nb - nab - nbc + nabc) + (nc - nac - nbc + nabc); // 둘만: 두 등대가 겹친 순간에는 셋이 모두 겹친 순간도 들어 있다 long two = (nab - nabc) + (nac - nabc) + (nbc - nabc); sb.append(one).append(' ').append(two).append(' ').append(nabc).append('\n'); } System.out.print(sb); }}using System;using System.Text; class Program{ static long Gcd(long x, long y) { while (y != 0) (x, y) = (y, x % y); return x; } // 최소공배수. cap을 넘으면 cap + 1을 돌려준다("T초 안에는 한 번도 없다"는 뜻) static long Lcm(long x, long y, long cap) { long part = x / Gcd(x, y); // part * y가 cap보다 큰지를 곱하기 전에 나눗셈으로 묻는다: 곱하면 long도 넘친다 if (part > cap / y) return cap + 1; return part * y; } static void Main() { int q = int.Parse(Console.ReadLine()!.Trim()); var sb = new StringBuilder(); for (int i = 0; i < q; i++) { string[] p = Console.ReadLine()!.Split(' ', StringSplitOptions.RemoveEmptyEntries); long a = long.Parse(p[0]), b = long.Parse(p[1]), c = long.Parse(p[2]), t = long.Parse(p[3]); long ab = Lcm(a, b, t); long na = t / a, nb = t / b, nc = t / c; long nab = t / ab, nac = t / Lcm(a, c, t), nbc = t / Lcm(b, c, t); long nabc = t / Lcm(ab, c, t); // 한 등대만: 그 등대의 횟수에서 다른 등대와 겹친 것을 빼고, 두 번 뺀 '셋 모두'를 한 번 돌려준다 long one = (na - nab - nac + nabc) + (nb - nab - nbc + nabc) + (nc - nac - nbc + nabc); // 둘만: 두 등대가 겹친 순간에는 셋이 모두 겹친 순간도 들어 있다 long two = (nab - nabc) + (nac - nabc) + (nbc - nabc); sb.Append(one).Append(' ').Append(two).Append(' ').Append(nabc).Append('\n'); } Console.Write(sb); }}#include <iostream>#include <numeric> // 최소공배수. cap을 넘으면 cap + 1을 돌려준다("T초 안에는 한 번도 없다"는 뜻)// std::lcm(x, y)는 결과가 long long에 안 들어가면 정해지지 않은 동작이라 여기서는 쓰지 못한다long long lcm(long long x, long long y, long long cap) { long long part = x / std::gcd(x, y); // part * y가 cap보다 큰지를 곱하기 전에 나눗셈으로 묻는다: 곱하면 long long도 넘친다 if (part > cap / y) return cap + 1; return part * y;} int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int q; std::cin >> q; while (q--) { long long a, b, c, t; std::cin >> a >> b >> c >> t; long long ab = lcm(a, b, t); long long na = t / a, nb = t / b, nc = t / c; long long nab = t / ab, nac = t / lcm(a, c, t), nbc = t / lcm(b, c, t); long long nabc = t / lcm(ab, c, t); // 한 등대만: 그 등대의 횟수에서 다른 등대와 겹친 것을 빼고, 두 번 뺀 '셋 모두'를 한 번 돌려준다 long long one = (na - nab - nac + nabc) + (nb - nab - nbc + nabc) + (nc - nac - nbc + nabc); // 둘만: 두 등대가 겹친 순간에는 셋이 모두 겹친 순간도 들어 있다 long long two = (nab - nabc) + (nac - nabc) + (nbc - nabc); std::cout << one << ' ' << two << ' ' << nabc << '\n'; }}#include <stdio.h> static long long gcd(long long x, long long y) { while (y != 0) { long long r = x % y; x = y; y = r; } return x;} /* 최소공배수. cap을 넘으면 cap + 1을 돌려준다("T초 안에는 한 번도 없다"는 뜻) */static long long lcm(long long x, long long y, long long cap) { long long part = x / gcd(x, y); /* part * y가 cap보다 큰지를 곱하기 전에 나눗셈으로 묻는다: 곱하면 long long도 넘친다 */ if (part > cap / y) return cap + 1; return part * y;} int main(void) { int q; if (scanf("%d", &q) != 1) return 0; for (int i = 0; i < q; i++) { long long a, b, c, t; if (scanf("%lld %lld %lld %lld", &a, &b, &c, &t) != 4) return 0; long long ab = lcm(a, b, t); long long na = t / a, nb = t / b, nc = t / c; long long nab = t / ab, nac = t / lcm(a, c, t), nbc = t / lcm(b, c, t); long long nabc = t / lcm(ab, c, t); /* 한 등대만: 그 등대의 횟수에서 다른 등대와 겹친 것을 빼고, 두 번 뺀 '셋 모두'를 한 번 돌려준다 */ long long one = (na - nab - nac + nabc) + (nb - nab - nbc + nabc) + (nc - nac - nbc + nabc); /* 둘만: 두 등대가 겹친 순간에는 셋이 모두 겹친 순간도 들어 있다 */ long long two = (nab - nabc) + (nac - nabc) + (nbc - nabc); printf("%lld %lld %lld\n", one, two, nabc); } return 0;}최대공약수(x, y){ 当 (y != 0) { r = x % y; x = y; y = r; } 返回 x;} // 최소공배수. cap을 넘으면 cap + 1을 돌려준다("T초 안에는 한 번도 없다"는 뜻)// 크레이콘의 수는 넘쳐도 뒤집히지 않고 큰 수로 남으니, 곱한 다음에 견줘도 된다최소공배수(x, y, cap){ l = 数学.商(x, 최대공약수(x, y)) * y; 如果 (l > cap) { 返回 cap + 1; } 返回 l;} q = 控制台.读行().转数字();循环 (i = 0; i < q; i++){ v = 控制台.读数字(); a = v[0]; b = v[1]; c = v[2]; t = v[3]; ab = 최소공배수(a, b, t); // T초 안에 몇 번인지는 몫으로 센다 na = 数学.商(t, a); nb = 数学.商(t, b); nc = 数学.商(t, c); nab = 数学.商(t, ab); nac = 数学.商(t, 최소공배수(a, c, t)); nbc = 数学.商(t, 최소공배수(b, c, t)); nabc = 数学.商(t, 최소공배수(ab, c, t)); // 한 등대만: 그 등대의 횟수에서 다른 등대와 겹친 것을 빼고, 두 번 뺀 '셋 모두'를 한 번 돌려준다 one = na - nab - nac + nabc + (nb - nab - nbc + nabc) + (nc - nac - nbc + nabc); // 둘만: 두 등대가 겹친 순간에는 셋이 모두 겹친 순간도 들어 있다 two = nab - nabc + (nac - nabc) + (nbc - nabc); 控制台.输出(one + " " + two + " " + nabc);}