빨강 리본 a개, 파랑 리본 b개, 노랑 리본 c개가 있고, 리본마다 길이가 정해져 있다.
색마다 리본을 하나씩 골라 세 리본을 한 묶음으로 만든다.
묶음의 세 리본을 모두 같은 길이의 도막으로 남김없이 자르려고 한다. 도막의 길이는 정수다.
그렇게 자를 수 있는 도막의 길이 가운데 가장 긴 것을 그 묶음의 도막 길이라고 한다.
길이가 같아도 서로 다른 리본은 다른 리본으로 센다. 그래서 만들 수 있는 묶음은 모두 a × b × c가지다.
첫 줄에 a, b, c가 주어진다.
둘째 줄에 빨강 리본 a개의 길이, 셋째 줄에 파랑 리본 b개의 길이, 넷째 줄에 노랑 리본 c개의 길이가 주어진다.
다섯째 줄에 질문의 수 q가 주어지고, 다음 q줄에 질문 g가 한 줄에 하나씩 주어진다.
질문마다 도막 길이가 딱 g인 묶음이 몇 가지인지 출력한다.
입력
1 ≤ a, b, c ≤ 9000. 리본의 길이는 1 이상 9000 이하의 정수다. 1 ≤ q ≤ 1000. 1 ≤ g ≤ 9000. 한 줄에 있는 수들은 빈칸 하나로 띄워 주어진다
출력
질문마다 한 줄에 묶음의 수(쉼표 없이 숫자만)
예시 1 · stdin
4 2 3
6 12 9 6
4 6
12 18 8
5
1
2
3
6
4
stdout
4
10
2
6
2
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
묶음의 도막 길이는 세 길이의 최대공약수예요. 묶음을 하나하나 보면 많게는 9000 × 9000 × 9000 = 7290억 가지라서 끝나지 않아요. 대신 소수 체에서 배수를 지울 때 쓰던 반복, 곧 d, 2d, 3d, …만 건너뛰며 보는 반복으로 d마다 '길이가 d의 배수인 리본의 수'를 색별로 세요. d를 1부터 9000까지 모두 해도 9000 × (1 + 1/2 + 1/3 + …)이라서 색 하나에 약 9만 번이에요. 세 수를 곱하면 '세 길이가 모두 d의 배수인 묶음', 곧 최대공약수가 d, 2d, 3d, … 가운데 하나인 묶음의 수예요. 여기서 최대공약수가 2d, 3d, …인 묶음의 수를 빼면 딱 d인 묶음이 남아요. 그래서 d가 큰 쪽부터 채워요. Python은 sum(count[d::d])처럼 조각의 걸음으로 배수만 고르고, C·C++·Java·C#·JS·TS는 for (m = d; m <= LIMIT; m += d)로, 크레이콘은 반복 (m = d; m <= 한계; m += d)로 건너뛰어요. 가장 큰 답은 9000 × 9000 × 9000 = 729000000000이라서 C·C++은 long long, Java·C#은 long에 담아요. JS·TS의 number와 크레이콘의 수는 2^53까지 정확해서 그대로 써요. 함정 하나: 빼기를 빠뜨리면 '최대공약수가 d의 배수인 묶음'을 답하게 돼요. 예시의 g = 2에서 10이 아니라 18이 나와요. 함정 둘: d가 작은 쪽부터 채우면 빼야 할 2d, 3d, …의 답이 아직 0이라서 아무것도 빠지지 않아요. 예시에서 똑같이 18이 나와요. 함정 셋: 길이가 같은 리본도 서로 다른 리본이에요. 길이의 종류만 세면 예시의 g = 2가 6이 돼요(빨강에 길이 6이 둘 있어요). 함정 넷: Java에서 세 수를 int끼리 곱하면 곱이 2^31을 넘을 때 넘친 값이 long에 담겨요. 예시는 수가 작아서 드러나지 않아요. 함정 다섯: 크레이콘에서 묶음을 하나하나 세면 큰 입력에서 '너무 오래 걸려서'라는 말과 함께 멈춰요. 길이가 같은 리본을 한데 모은 뒤 두 색씩 최대공약수를 세는 방법(최대공약수 계산이 많게는 1억 6천만 번)도 C로 재 보니 약 4초가 걸려 제한 시간 2초를 넘었어요. 한편 건너뛰지 않고 d마다 1부터 9000까지를 모두 보며 m % d == 0인 것만 고르는 풀이(약 8천만 번)는 C로 0.1초면 끝나요. 같은 풀이가 Python으로는 약 2초가 걸려 더 느린 채점기에서는 제한 시간을 넘을 수 있고, 크레이콘은 '너무 오래 걸려서'로 멈춰요. 그러니 건너뛰는 반복이 꼭 필요한 것은 느린 언어 쪽이고, 어느 언어에서나 꼭 있어야 하는 것은 배수로 세고 큰 쪽부터 빼는 생각이에요.
Pythonmain.py · 41 줄
import sysLIMIT = 9000def multiples_table(lengths): """table[d] = 길이가 d의 배수인 리본의 수""" count = [0] * (LIMIT + 1) for x in lengths: count[x] += 1 table = [0] * (LIMIT + 1) for d in range(1, LIMIT + 1): # 체처럼 d의 배수만 건너뛰며 본다: 모두 합쳐 LIMIT × (1 + 1/2 + 1/3 + …) 번 table[d] = sum(count[d::d]) return tabledef main(): data = sys.stdin.read().split() a, b, c = int(data[0]), int(data[1]), int(data[2]) pos = 3 red = multiples_table(map(int, data[pos:pos + a])) pos += a blue = multiples_table(map(int, data[pos:pos + b])) pos += b yellow = multiples_table(map(int, data[pos:pos + c])) pos += c # exact[d] = 가장 긴 도막이 딱 d인 묶음의 수 exact = [0] * (LIMIT + 1) for d in range(LIMIT, 0, -1): # 큰 d부터: 2d, 3d, …의 답이 먼저 정해져 있어야 한다 total = red[d] * blue[d] * yellow[d] # 세 길이가 모두 d의 배수인 묶음 total -= sum(exact[2 * d::d]) # 그 가운데 최대공약수가 2d, 3d, …인 묶음을 뺀다 exact[d] = total q = int(data[pos]) out = [str(exact[int(g)]) for g in data[pos + 1:pos + 1 + q]] print("\n".join(out))main()
JavaScriptmain.js · 32 줄
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);const LIMIT = 9000;let pos = 0;const a = data[pos++], b = data[pos++], c = data[pos++];// table[d] = 길이가 d의 배수인 리본의 수function multiplesTable(n) { const count = new Array(LIMIT + 1).fill(0); for (let i = 0; i < n; i++) count[data[pos++]]++; const table = new Array(LIMIT + 1).fill(0); for (let d = 1; d <= LIMIT; d++) { for (let m = d; m <= LIMIT; m += d) table[d] += count[m]; // d의 배수만 건너뛰며 본다 } return table;}const red = multiplesTable(a);const blue = multiplesTable(b);const yellow = multiplesTable(c);// exact[d] = 가장 긴 도막이 딱 d인 묶음의 수. 9000^3은 2^53보다 작아 number로 정확하다const exact = new Array(LIMIT + 1).fill(0);for (let d = LIMIT; d >= 1; d--) { // 큰 d부터 let total = red[d] * blue[d] * yellow[d]; for (let m = 2 * d; m <= LIMIT; m += d) total -= exact[m]; exact[d] = total;}const q = data[pos++];const out = [];for (let i = 0; i < q; i++) out.push(exact[data[pos++]]);console.log(out.join("\n"));
TypeScriptmain.ts · 33 줄
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);const LIMIT = 9000;let pos = 0;const a = data[pos++], b = data[pos++], c = data[pos++];// table[d] = 길이가 d의 배수인 리본의 수function multiplesTable(n: number): number[] { const count: number[] = new Array<number>(LIMIT + 1).fill(0); for (let i = 0; i < n; i++) count[data[pos++]]++; const table: number[] = new Array<number>(LIMIT + 1).fill(0); for (let d = 1; d <= LIMIT; d++) { for (let m = d; m <= LIMIT; m += d) table[d] += count[m]; // d의 배수만 건너뛰며 본다 } return table;}const red = multiplesTable(a);const blue = multiplesTable(b);const yellow = multiplesTable(c);// exact[d] = 가장 긴 도막이 딱 d인 묶음의 수. 9000^3은 2^53보다 작아 number로 정확하다const exact: number[] = new Array<number>(LIMIT + 1).fill(0);for (let d = LIMIT; d >= 1; d--) { // 큰 d부터 let total = red[d] * blue[d] * yellow[d]; for (let m = 2 * d; m <= LIMIT; m += d) total -= exact[m]; exact[d] = total;}const q = data[pos++];const out: number[] = [];for (let i = 0; i < q; i++) out.push(exact[data[pos++]]);console.log(out.join("\n"));
JavaMain.java · 44 줄
import java.io.*;import java.util.*;public class Main { static final int LIMIT = 9000; static StreamTokenizer in; static int next() throws IOException { in.nextToken(); return (int) in.nval; } // table[d] = 길이가 d의 배수인 리본의 수 static long[] multiplesTable(int n) throws IOException { int[] count = new int[LIMIT + 1]; for (int i = 0; i < n; i++) count[next()]++; long[] table = new long[LIMIT + 1]; for (int d = 1; d <= LIMIT; d++) { for (int m = d; m <= LIMIT; m += d) table[d] += count[m]; // d의 배수만 건너뛰며 본다 } return table; } public static void main(String[] args) throws IOException { in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); int a = next(), b = next(), c = next(); long[] red = multiplesTable(a); long[] blue = multiplesTable(b); long[] yellow = multiplesTable(c); // exact[d] = 가장 긴 도막이 딱 d인 묶음의 수. 9000^3은 int를 넘으므로 long long[] exact = new long[LIMIT + 1]; for (int d = LIMIT; d >= 1; d--) { // 큰 d부터 long total = red[d] * blue[d] * yellow[d]; for (int m = 2 * d; m <= LIMIT; m += d) total -= exact[m]; exact[d] = total; } int q = next(); StringBuilder out = new StringBuilder(); for (int i = 0; i < q; i++) out.append(exact[next()]).append('\n'); System.out.print(out); }}
C#Main.cs · 45 줄
using System;using System.Text;class Program{ const int Limit = 9000; static string[] tokens; static int pos = 0; // table[d] = 길이가 d의 배수인 리본의 수 static long[] MultiplesTable(int n) { var count = new int[Limit + 1]; for (int i = 0; i < n; i++) count[int.Parse(tokens[pos++])]++; var table = new long[Limit + 1]; for (int d = 1; d <= Limit; d++) { for (int m = d; m <= Limit; m += d) table[d] += count[m]; // d의 배수만 건너뛰며 본다 } return table; } static void Main() { tokens = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); int a = int.Parse(tokens[pos++]), b = int.Parse(tokens[pos++]), c = int.Parse(tokens[pos++]); long[] red = MultiplesTable(a); long[] blue = MultiplesTable(b); long[] yellow = MultiplesTable(c); // exact[d] = 가장 긴 도막이 딱 d인 묶음의 수. 9000^3은 int를 넘으므로 long var exact = new long[Limit + 1]; for (int d = Limit; d >= 1; d--) // 큰 d부터 { long total = red[d] * blue[d] * yellow[d]; for (int m = 2 * d; m <= Limit; m += d) total -= exact[m]; exact[d] = total; } int q = int.Parse(tokens[pos++]); var output = new StringBuilder(); for (int i = 0; i < q; i++) output.Append(exact[int.Parse(tokens[pos++])]).Append('\n'); Console.Write(output); }}
C++main.cpp · 45 줄
#include <iostream>#include <vector>const int LIMIT = 9000;// table[d] = 길이가 d의 배수인 리본의 수std::vector<long long> multiplesTable(int n) { std::vector<int> count(LIMIT + 1, 0); for (int i = 0; i < n; i++) { int x; std::cin >> x; count[x]++; } std::vector<long long> table(LIMIT + 1, 0); for (int d = 1; d <= LIMIT; d++) { for (int m = d; m <= LIMIT; m += d) table[d] += count[m]; // d의 배수만 건너뛰며 본다 } return table;}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int a, b, c; std::cin >> a >> b >> c; std::vector<long long> red = multiplesTable(a); std::vector<long long> blue = multiplesTable(b); std::vector<long long> yellow = multiplesTable(c); // exact[d] = 가장 긴 도막이 딱 d인 묶음의 수. 9000^3은 int를 넘으므로 long long std::vector<long long> exact(LIMIT + 1, 0); for (int d = LIMIT; d >= 1; d--) { // 큰 d부터 long long total = red[d] * blue[d] * yellow[d]; for (int m = 2 * d; m <= LIMIT; m += d) total -= exact[m]; exact[d] = total; } int q; std::cin >> q; for (int i = 0; i < q; i++) { int g; std::cin >> g; std::cout << exact[g] << '\n'; }}
Cmain.c · 43 줄
#include <stdio.h>#define LIMIT 9000static int count[LIMIT + 1];static long long red[LIMIT + 1], blue[LIMIT + 1], yellow[LIMIT + 1], exact[LIMIT + 1];/* table[d] = 길이가 d의 배수인 리본의 수 */static void multiples_table(int n, long long *table) { for (int i = 0; i <= LIMIT; i++) count[i] = 0; for (int i = 0; i < n; i++) { int x; if (scanf("%d", &x) != 1) return; count[x]++; } for (int d = 1; d <= LIMIT; d++) { table[d] = 0; for (int m = d; m <= LIMIT; m += d) table[d] += count[m]; /* d의 배수만 건너뛰며 본다 */ }}int main(void) { int a, b, c, q; if (scanf("%d %d %d", &a, &b, &c) != 3) return 0; multiples_table(a, red); multiples_table(b, blue); multiples_table(c, yellow); /* exact[d] = 가장 긴 도막이 딱 d인 묶음의 수. 9000^3은 int를 넘으므로 long long */ for (int d = LIMIT; d >= 1; d--) { /* 큰 d부터 */ long long total = red[d] * blue[d] * yellow[d]; for (int m = 2 * d; m <= LIMIT; m += d) total -= exact[m]; exact[d] = total; } if (scanf("%d", &q) != 1) return 0; for (int i = 0; i < q; i++) { int g; if (scanf("%d", &g) != 1) return 0; printf("%lld\n", exact[g]); } return 0;}
Craykonmain.cray · 47 줄
// 표[d] = 길이가 d의 배수인 리본의 수배수표(길이들, 한계){ 수 = 새목록(한계 + 1, 0); 각각 (x 에서 길이들) { 수[x] += 1; } 표 = 새목록(한계 + 1, 0); 반복 (d = 1; d <= 한계; d++) { 합 = 0; 반복 (m = d; m <= 한계; m += d) { 합 += 수[m]; } 표[d] = 합; } 돌려주기 표;}한계 = 9000;콘솔.줄읽기(); // a b c: 줄마다 통째로 읽으니 개수는 쓰지 않는다빨강 = 배수표(콘솔.수들읽기(), 한계);파랑 = 배수표(콘솔.수들읽기(), 한계);노랑 = 배수표(콘솔.수들읽기(), 한계);// 딱[d] = 가장 긴 도막이 딱 d인 묶음의 수. 9000^3은 2^53보다 작아 정확하다딱 = 새목록(한계 + 1, 0);반복 (d = 한계; d >= 1; d--){ 모두 = 빨강[d] * 파랑[d] * 노랑[d]; 반복 (m = 2 * d; m <= 한계; m += d) { 모두 -= 딱[m]; } 딱[d] = 모두;}q = 콘솔.줄읽기().수로변환();out = [];반복 (i = 0; i < q; i++){ g = 콘솔.줄읽기().수로변환(); out.넣기(딱[g]);}콘솔.쓰기(out.잇기("\n"));