T は 10^15 まであるので、1 秒ずつ数えることはできません。 周期 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 秒は 24 秒ではなく 12 秒ごとに重なります。 落とし穴その二：二つの灯台が重なる回数には、三つすべてが重なる瞬間も入っています。 例の最初の質問で二つずつ重なる回数は 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) で求めます。
Pythonmain.py · 25 行
import mathimport sysdef 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()
JavaScriptmain.js · 30 行
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"));
TypeScriptmain.ts · 32 行
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"));
JavaMain.java · 44 行
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); }}
C#Main.cs · 41 行
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); }}
C++main.cpp · 31 行
#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'; }}
Cmain.c · 37 行
#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;}
Craykonmain.cray · 46 行
최대공약수(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);}