有 a 条红丝带、b 条蓝丝带、c 条黄丝带，每条丝带都有确定的长度。
每种颜色各选一条丝带，三条丝带组成一组。
要把这一组的三条丝带全部剪成长度相同的小段，并且不能有剩余。
小段的长度是整数。
能这样剪的小段长度中最长的那个，叫做这一组的小段长度。
长度相同的不同丝带也算作不同的丝带。
所以能组成的组一共有 a × b × c 种。
第一行给出 a、b、c。
第二行给出 a 条红丝带的长度，第三行给出 b 条蓝丝带的长度，第四行给出 c 条黄丝带的长度。
第五行给出询问的个数 q，接下来 q 行每行给出一个询问 g。
对每个询问，输出小段长度恰好是 g 的组有多少种。
4 2 3 6 12 9 6 4 6 12 18 8 5 1 2 3 6 4
4 10 2 6 2
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
一组的小段长度就是三个长度的最大公约数。
一组一组地看，最多有 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) 跳着走，Craykon 用 循环 (m = d; m <= limit; m += d)。
最大的答案是 9000 × 9000 × 9000 = 729000000000，所以 C、C++ 用 long long，Java、C# 用 long 来存。
JS、TS 的 number 和 Craykon 的数在 2^53 以内是精确的，直接用。
陷阱一：漏掉减法，答的就是“最大公约数是 d 的倍数的组”。
示例的 g = 2 会得到 18 而不是 10。
陷阱二：从小的 d 开始填，该减的 2d、3d、… 的答案还是 0，什么也没减掉。
示例里同样得到 18。
陷阱三：长度相同的丝带也是不同的丝带。
只数长度的种类，示例的 g = 2 会变成 6（红色里有两条长度为 6 的）。
陷阱四：在 Java 里把三个数按 int 相乘，乘积超过 2^31 时溢出后的值才放进 long。
示例的数太小，看不出来。
陷阱五：在 Craykon 里一组一组地数，遇到大的输入会带着“耗时太长”的提示停止。
先把长度相同的丝带合并、再两种颜色两种颜色地数最大公约数的做法（最大公约数最多要算 1.6 亿次），用 C 实测也要约 4 秒，超过了 2 秒的时间限制。
另一方面，不跳着走、对每个 d 把 1 到 9000 全看一遍、只挑出 m % d == 0 的做法（约 8 千万次），用 C 只要 0.1 秒。
同样的做法用 Python 要约 2 秒，在更慢的评测机上可能超时，Craykon 则会因“耗时太长”而停止。
所以跳着走的循环只有在慢的语言里才非用不可，而无论哪种语言都少不了的，是按倍数来数、再从大的一端往下减的想法。
import sys LIMIT = 9000 def 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 table def 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()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"));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"));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); }}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); }}#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'; }}#include <stdio.h> #define LIMIT 9000 static 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;}// 표[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"));