등대 세 개가 0초에 함께 한 번 깜빡인 뒤, 첫째 등대는 a초마다, 둘째 등대는 b초마다, 셋째 등대는 c초마다 깜빡인다.
곧 첫째 등대는 a초, 2a초, 3a초, …에 깜빡이고, 둘째와 셋째 등대도 같은 식이다.
1초부터 T초까지(1초와 T초 포함)의 정수 초 가운데 다음 세 가지 순간이 각각 몇 번인지 구하라.
첫째, 세 등대 가운데 정확히 하나만 깜빡이는 순간.
둘째, 정확히 둘이 함께 깜빡이는 순간.
셋째, 셋이 모두 함께 깜빡이는 순간.
0초는 세지 않는다.
주기가 같은 등대도 서로 다른 등대로 센다(a = b이면 첫째와 둘째 등대는 늘 함께 깜빡인다).
질문이 q개 주어지고, 질문마다 세 수를 위의 차례로 빈칸 하나씩 띄워 한 줄에 출력한다.
입력
첫 줄에 질문 수 q가 주어진다. 다음 q줄에 a, b, c, T가 빈칸 하나씩 띄워 주어진다. 1 ≤ q ≤ 1,000, 1 ≤ a, b, c ≤ 10^9, 1 ≤ T ≤ 10^15
출력
질문마다 한 줄에 '하나만 깜빡이는 순간의 수', '둘만 깜빡이는 순간의 수', '셋이 모두 깜빡이는 순간의 수'를 빈칸 하나씩 띄워 출력한다
예시 1 · stdin
2
4 6 9 36
2 2 5 9
stdout
10 3 1
1 4 0
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
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와 크레이콘의 수는 2^53(약 9 × 10^15)까지만 정확하지만, 넘쳐도 뒤집히지 않고 큰 수로 남아요. T 이하인 값은 모두 정확하니 곱한 다음 l > T로 견주면 돼요. 몫은 JavaScript Math.floor(t / l), 크레이콘 수학.몫(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);}