赤いリボンが 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()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 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) で、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 で 10 ではなく 18 が出ます。 罠その二：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 は「時間がかかりすぎ」で止まります。 つまり飛び飛びの繰り返しがどうしても要るのは遅い言語のほうで、どの言語でも欠かせないのは、倍数で数えて大きいほうから引くという考え方です。
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"));