Three lighthouses flash once together at second 0. After that the first flashes every a seconds, the second every b seconds and the third every c seconds.
That is, the first lighthouse flashes at seconds a, 2a, 3a, …, and likewise for the second and the third.
Among the whole seconds from 1 to T (both included), count how many moments there are of each of the following three kinds.
First, moments when exactly one of the three lighthouses flashes.
Second, moments when exactly two flash together.
Third, moments when all three flash together.
Second 0 is not counted.
Lighthouses with the same period are still different lighthouses (if a = b, the first and the second always flash together).
There are q questions; for each one print the three numbers in the order above on one line, separated by single spaces.
Input
The first line has the number of questions q. Each of the next q lines has a, b, c and T separated by single spaces. 1 ≤ q ≤ 1,000, 1 ≤ a, b, c ≤ 10^9, 1 ≤ T ≤ 10^15
Output
For each question, one line with the number of moments when exactly one flashes, when exactly two flash, and when all three flash, separated by single spaces
Example 1 · stdin
2
4 6 9 36
2 2 5 9
stdout
10 3 1
1 4 0
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
T can be 10^15, so you cannot step through the seconds one by one. A lighthouse with period a flashes T divided by a, rounded down times within T seconds, and two lighthouses flash together once every least common multiple of their periods. The least common multiple is a ÷ gcd(a, b) × b. For the greatest common divisor there are Python math.gcd and C++ std::gcd (<numeric>); in the other languages you write a function that repeats the remainder with while (y != 0). Python even gives the least common multiple of all three at once with math.lcm(a, b, c). Trap one: using the product of two periods as the common period is wrong. Periods 4 and 6 meet every 12 seconds, not every 24. Trap two: the moments when two lighthouses coincide include the moments when all three coincide. In the first question of the example the pairs coincide 3 + 1 + 2 = 6 times, but second 36 is in all three pairs, so 'exactly two' is 6 − 3 × 1 = 3. Trap three: the periods fit in an int, but a least common multiple can be as large as 10^18. Computing it as int in Java, C#, C or C++ overflows (use long or long long). Trap four: the least common multiple of all three can reach 10^27, which does not fit in a long either. A long in Java and C# wraps around silently on overflow and can turn into some unrelated number smaller than T, and in C and C++ it is undefined behaviour. So before multiplying, ask with a division whether part > T / y; if the result would exceed T, do not multiply and treat it as 'zero times'. Python integers have no size limit, so you can just multiply. A JavaScript/TypeScript number and a Craykon number are exact only up to 2^53 (about 9 × 10^15), but on overflow they do not wrap around; they stay large. Every value up to T is exact, so you can multiply first and then compare with l > T. The quotient is JavaScript Math.floor(t / l) and Craykon Mathf.Quot(t, l).
Pythonmain.py · 25 lines
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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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 lines
최대공약수(x, y){ while (y != 0) { r = x % y; x = y; y = r; } return x;}// 최소공배수. cap을 넘으면 cap + 1을 돌려준다("T초 안에는 한 번도 없다"는 뜻)// 크레이콘의 수는 넘쳐도 뒤집히지 않고 큰 수로 남으니, 곱한 다음에 견줘도 된다최소공배수(x, y, cap){ l = Mathf.Quot(x, 최대공약수(x, y)) * y; if (l > cap) { return cap + 1; } return l;}q = Console.ReadLine().ToNumber();for (i = 0; i < q; i++){ v = Console.ReadNumbers(); a = v[0]; b = v[1]; c = v[2]; t = v[3]; ab = 최소공배수(a, b, t); // T초 안에 몇 번인지는 몫으로 센다 na = Mathf.Quot(t, a); nb = Mathf.Quot(t, b); nc = Mathf.Quot(t, c); nab = Mathf.Quot(t, ab); nac = Mathf.Quot(t, 최소공배수(a, c, t)); nbc = Mathf.Quot(t, 최소공배수(b, c, t)); nabc = Mathf.Quot(t, 최소공배수(ab, c, t)); // 한 등대만: 그 등대의 횟수에서 다른 등대와 겹친 것을 빼고, 두 번 뺀 '셋 모두'를 한 번 돌려준다 one = na - nab - nac + nabc + (nb - nab - nbc + nabc) + (nc - nac - nbc + nabc); // 둘만: 두 등대가 겹친 순간에는 셋이 모두 겹친 순간도 들어 있다 two = nab - nabc + (nac - nabc) + (nbc - nabc); Console.WriteLine(one + " " + two + " " + nabc);}