There are a red ribbons, b blue ribbons and c yellow ribbons, and each ribbon has a length.
Pick one ribbon of each color to make a bundle of three ribbons.
All three ribbons of the bundle are to be cut, with nothing left over, into pieces of one same length. The piece length is an integer.
The longest piece length that makes this possible is called the piece length of the bundle.
Ribbons with the same length still count as different ribbons. So there are a × b × c possible bundles in all.
The first line gives a, b and c.
The second line gives the lengths of the a red ribbons, the third line the lengths of the b blue ribbons, and the fourth line the lengths of the c yellow ribbons.
The fifth line gives the number of questions q, and each of the next q lines gives one question g.
For each question, print how many bundles have a piece length of exactly g.
Input
1 ≤ a, b, c ≤ 9000. Each ribbon length is an integer from 1 to 9000. 1 ≤ q ≤ 1000. 1 ≤ g ≤ 9000. Numbers on one line are separated by single spaces
Output
One line per question with the number of bundles (plain digits without commas)
Example 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
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
The piece length of a bundle is the greatest common divisor of its three lengths. Looking at bundles one by one means up to 9000 × 9000 × 9000 = 729 billion of them, which never finishes. Instead, use the loop that crosses out multiples in a prime sieve, the one that visits only d, 2d, 3d, …, to count for every d 'how many ribbons have a length that is a multiple of d', color by color. Doing that for every d from 1 to 9000 costs 9000 × (1 + 1/2 + 1/3 + …), about 90 thousand steps per color. The product of the three counts is the number of bundles whose three lengths are all multiples of d, that is, bundles whose gcd is one of d, 2d, 3d, …. Subtracting the bundles whose gcd is 2d, 3d, … leaves those with exactly d. That is why d is filled in from the large end. Python picks the multiples with a slice step, sum(count[d::d]); C, C++, Java, C#, JS and TS skip with for (m = d; m <= LIMIT; m += d), and Craykon with for (m = d; m <= limit; m += d). The largest answer is 9000 × 9000 × 9000 = 729000000000, so C/C++ hold it in long long and Java/C# in long. A JS/TS number and a Craykon number are exact up to 2^53 and are used as they are. Trap one: without the subtraction you answer 'bundles whose gcd is a multiple of d'. For g = 2 in the example you get 18 instead of 10. Trap two: filling d from the small end means the answers for 2d, 3d, … that should be subtracted are still 0, so nothing is removed. The example gives the same 18. Trap three: ribbons of the same length are still different ribbons. Counting only the kinds of lengths makes g = 2 in the example 6 (red has two ribbons of length 6). Trap four: in Java, multiplying the three counts as ints stores an overflowed value in the long once the product passes 2^31. The example's numbers are too small to show it. Trap five: counting bundles one by one in Craykon stops on large inputs with a 'Took too long' message. Merging ribbons of the same length and then counting gcds two colors at a time (up to 160 million gcd computations) also took about 4 seconds when measured in C, over the 2-second limit. On the other hand, a solution that does not skip, but for every d looks at all of 1 to 9000 and keeps those with m % d == 0 (about 80 million steps), finishes in 0.1 seconds in C. The same solution took about 2 seconds in Python, which can pass the limit on the slower judge, and Craykon stops with 'Took too long'. So the skipping loop is really needed only in the slow languages; what every language needs is the idea of counting by multiples and subtracting from the large end.
Pythonmain.py · 41 lines
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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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 lines
// 표[d] = 길이가 d의 배수인 리본의 수배수표(길이들, 한계){ 수 = NewList(한계 + 1, 0); foreach (x in 길이들) { 수[x] += 1; } 표 = NewList(한계 + 1, 0); for (d = 1; d <= 한계; d++) { 합 = 0; for (m = d; m <= 한계; m += d) { 합 += 수[m]; } 표[d] = 합; } return 표;}한계 = 9000;Console.ReadLine(); // a b c: 줄마다 통째로 읽으니 개수는 쓰지 않는다빨강 = 배수표(Console.ReadNumbers(), 한계);파랑 = 배수표(Console.ReadNumbers(), 한계);노랑 = 배수표(Console.ReadNumbers(), 한계);// 딱[d] = 가장 긴 도막이 딱 d인 묶음의 수. 9000^3은 2^53보다 작아 정확하다딱 = NewList(한계 + 1, 0);for (d = 한계; d >= 1; d--){ 모두 = 빨강[d] * 파랑[d] * 노랑[d]; for (m = 2 * d; m <= 한계; m += d) { 모두 -= 딱[m]; } 딱[d] = 모두;}q = Console.ReadLine().ToNumber();out = [];for (i = 0; i < q; i++){ g = Console.ReadLine().ToNumber(); out.Add(딱[g]);}Console.WriteLine(out.Join("\n"));