大于 1 的整数可以表示成质数的乘积。 例如 48 = 2 × 2 × 2 × 2 × 3，49 = 7 × 7。 把整数 x 表示成质数的乘积时，如果用到的质数都不超过 B，就把 x 叫做“能被 B 分开的数”。 1 一个质数也不用，所以无论 B 是多少，它都是能被 B 分开的数。 例如 48 是能被 3 分开的数，49 是能被 7 分开的数，但不是能被 5 分开的数。 给出 q 个询问，每个询问是三个整数 L、R、B。 对每个询问，在 L 到 R（含两端）的整数中找出所有能被 B 分开的数。 如果有这样的数，在一行中输出它们的个数、最小的一个和最大的一个，用一个空格隔开。 如果一个也没有，只输出 0。
输入
第一行给出 q，接下来 q 行每行给出用一个空格隔开的 L、R、B。 1 ≤ q ≤ 100，1 ≤ L ≤ R ≤ 81,000,000，R − L ≤ 8,999，1 ≤ B ≤ 81,000,000。 全部是整数
输出
每个询问一行：能被 B 分开的数的个数、最小的一个和最大的一个（只写数字，不加逗号），或者 0
样例 1 · stdin
4
1 10 3
48 50 7
18000 18004 9001
14 14 5
stdout
7 1 9
3 48 50
5 18000 18004
0
main.py
错误列表00F8 ↓ · ⇧F8 ↑
输入(stdin)
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
其他语言怎么写？查看各语言题解 · 8 种语言题解
数最大到 8100 万，没法对全部的数做筛法，但一个窗口里只有 9,000 个数。 所以只用埃拉托斯特尼筛法求出 9,000 以内的质数，然后在窗口里直接跳到质数 p 的倍数的位置，用 p 去除（区间筛）。 如果对每个数逐个试除质数，一个窗口最多要除一千万次左右，而这样做几万次就够了。 老实说，在 C、C++ 这样快的语言里，对每个数试除到 p × p 大于剩下的数就停，也能在时限内跑完。 在 Python 和 Craykon 里那样做会超时，所以必须用区间筛。 为什么是 9,000？ 因为 9,000 × 9,000 = 81,000,000，大于 9,000 的质数在一个数里最多只出现一次。 所以用不超过 B 的小质数尽量除，再看“剩下的数”是否不超过 B 就行。 剩下的数要么是 1，要么是一个大于 9,000 的质数，要么是若干大于 B 的质数的乘积。 陷阱一：每个质数只除一次的话，8 = 2 × 2 × 2 会剩下 4，第一个询问变成 6 1 9。 陷阱二：只在剩下 1 时才计数，会漏掉 18002 = 2 × 9001，第三个询问变成 4 个。 陷阱三：是“不超过 B”。 写成“小于”的话，第一个询问里用不了 3，变成 4 1 8。 陷阱四：1 也要算。 去掉它会变成 6 2 9。 陷阱五：窗口里 p 的第一个倍数必须不小于 L。 写成 L / p * p + p 的话，L 是 p 的倍数时会跳过 L，第二个询问变成 2 49 50。 陷阱六：整数除法。 (L + p - 1) / p * p 在 Java、C#、C、C++ 中因为 / 得到商所以是对的，但 JS、TS、Craykon 的 / 会除出小数，结果就是 L + p − 1，第二个询问变成 0。 JS、TS 用 Math.ceil(L / p) * p 或 Math.floor，Craykon 用 数学.商(L + p - 1, p) * p，Python 用 //。 陷阱七：如果小质数只求到 1,000，像 1009 × 1013 = 1,022,117 这样的数会整个剩下。 B = 2,000 时它是能被分开的数，却会回答不是。
Pythonmain.py · 43 行
import sysROOT = 9000 # 9000 × 9000 = 81,000,000: 이보다 큰 소수는 한 수에 많아야 한 번 들어 있다def main(): data = sys.stdin.read().split() q = int(data[0]) # 에라토스테네스의 체로 9,000 이하의 소수를 모은다 is_prime = [True] * (ROOT + 1) is_prime[0] = is_prime[1] = False primes = [] for i in range(2, ROOT + 1): if is_prime[i]: primes.append(i) for j in range(i * i, ROOT + 1, i): is_prime[j] = False out = [] for i in range(q): lo, hi, b = int(data[1 + 3 * i]), int(data[2 + 3 * i]), int(data[3 + 3 * i]) # rest[x - lo]: x에서 b 이하의 작은 소수를 모두 나누어 없애고 남은 수 rest = list(range(lo, hi + 1)) for p in primes: if p > b: break first = (lo + p - 1) // p * p # lo 이상인 첫 p의 배수 for x in range(first, hi + 1, p): r = rest[x - lo] while r % p == 0: r //= p rest[x - lo] = r # 남은 수가 1이 아니면 9,000보다 큰 소수 하나이거나, b보다 큰 소수들의 곱이다 good = [lo + k for k, r in enumerate(rest) if r <= b] if good: out.append(f"{len(good)} {good[0]} {good[-1]}") else: out.append("0") print("\n".join(out))main()
JavaScriptmain.js · 42 行
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);const q = data[0];const ROOT = 9000; // 9000 × 9000 = 81,000,000: 이보다 큰 소수는 한 수에 많아야 한 번 들어 있다// 에라토스테네스의 체로 9,000 이하의 소수를 모은다const isPrime = new Array(ROOT + 1).fill(true);isPrime[0] = isPrime[1] = false;const primes = [];for (let i = 2; i <= ROOT; i++) { if (isPrime[i]) { primes.push(i); for (let j = i * i; j <= ROOT; j += i) isPrime[j] = false; }}const out = [];for (let i = 0; i < q; i++) { const lo = data[1 + 3 * i], hi = data[2 + 3 * i], b = data[3 + 3 * i]; // rest[x - lo]: x에서 b 이하의 작은 소수를 모두 나누어 없애고 남은 수 const rest = []; for (let x = lo; x <= hi; x++) rest.push(x); for (const p of primes) { if (p > b) break; const first = Math.ceil(lo / p) * p; // lo 이상인 첫 p의 배수. `/`는 소수가 나오므로 올림한다 for (let x = first; x <= hi; x += p) { let r = rest[x - lo]; while (r % p === 0) r /= p; rest[x - lo] = r; } } // 남은 수가 1이 아니면 9,000보다 큰 소수 하나이거나, b보다 큰 소수들의 곱이다 let count = 0, smallest = 0, largest = 0; for (let x = lo; x <= hi; x++) { if (rest[x - lo] <= b) { if (count === 0) smallest = x; largest = x; count++; } } out.push(count > 0 ? `${count} ${smallest} ${largest}` : "0");}console.log(out.join("\n"));
TypeScriptmain.ts · 42 行
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);const q = data[0];const ROOT = 9000; // 9000 × 9000 = 81,000,000: 이보다 큰 소수는 한 수에 많아야 한 번 들어 있다// 에라토스테네스의 체로 9,000 이하의 소수를 모은다const isPrime: boolean[] = new Array(ROOT + 1).fill(true);isPrime[0] = isPrime[1] = false;const primes: number[] = [];for (let i = 2; i <= ROOT; i++) { if (isPrime[i]) { primes.push(i); for (let j = i * i; j <= ROOT; j += i) isPrime[j] = false; }}const out: string[] = [];for (let i = 0; i < q; i++) { const lo = data[1 + 3 * i], hi = data[2 + 3 * i], b = data[3 + 3 * i]; // rest[x - lo]: x에서 b 이하의 작은 소수를 모두 나누어 없애고 남은 수 const rest: number[] = []; for (let x = lo; x <= hi; x++) rest.push(x); for (const p of primes) { if (p > b) break; const first = Math.ceil(lo / p) * p; // lo 이상인 첫 p의 배수. `/`는 소수가 나오므로 올림한다 for (let x = first; x <= hi; x += p) { let r = rest[x - lo]; while (r % p === 0) r /= p; rest[x - lo] = r; } } // 남은 수가 1이 아니면 9,000보다 큰 소수 하나이거나, b보다 큰 소수들의 곱이다 let count = 0, smallest = 0, largest = 0; for (let x = lo; x <= hi; x++) { if (rest[x - lo] <= b) { if (count === 0) smallest = x; largest = x; count++; } } out.push(count > 0 ? `${count} ${smallest} ${largest}` : "0");}console.log(out.join("\n"));
JavaMain.java · 49 行
import java.util.*;public class Main { static final int ROOT = 9000; // 9000 × 9000 = 81,000,000: 이보다 큰 소수는 한 수에 많아야 한 번 들어 있다 public static void main(String[] args) { Scanner in = new Scanner(System.in); int q = in.nextInt(); // 에라토스테네스의 체로 9,000 이하의 소수를 모은다 boolean[] composite = new boolean[ROOT + 1]; List<Integer> primes = new ArrayList<>(); for (int i = 2; i <= ROOT; i++) { if (!composite[i]) { primes.add(i); for (int j = i * i; j <= ROOT; j += i) composite[j] = true; } } StringBuilder out = new StringBuilder(); for (int i = 0; i < q; i++) { int lo = in.nextInt(), hi = in.nextInt(), b = in.nextInt(); // rest[x - lo]: x에서 b 이하의 작은 소수를 모두 나누어 없애고 남은 수 int[] rest = new int[hi - lo + 1]; for (int x = lo; x <= hi; x++) rest[x - lo] = x; for (int p : primes) { if (p > b) break; int first = (lo + p - 1) / p * p; // lo 이상인 첫 p의 배수(정수 나눗셈) for (int x = first; x <= hi; x += p) { int r = rest[x - lo]; while (r % p == 0) r /= p; rest[x - lo] = r; } } // 남은 수가 1이 아니면 9,000보다 큰 소수 하나이거나, b보다 큰 소수들의 곱이다 int count = 0, smallest = 0, largest = 0; for (int x = lo; x <= hi; x++) { if (rest[x - lo] <= b) { if (count == 0) smallest = x; largest = x; count++; } } if (count > 0) out.append(count).append(' ').append(smallest).append(' ').append(largest).append('\n'); else out.append("0\n"); } System.out.print(out); }}
C#Main.cs · 60 行
using System;using System.Collections.Generic;using System.Text;class Program{ const int Root = 9000; // 9000 × 9000 = 81,000,000: 이보다 큰 소수는 한 수에 많아야 한 번 들어 있다 static void Main() { string[] data = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); int q = int.Parse(data[0]); // 에라토스테네스의 체로 9,000 이하의 소수를 모은다 var composite = new bool[Root + 1]; var primes = new List<int>(); for (int i = 2; i <= Root; i++) { if (!composite[i]) { primes.Add(i); for (int j = i * i; j <= Root; j += i) composite[j] = true; } } var output = new StringBuilder(); for (int i = 0; i < q; i++) { int lo = int.Parse(data[1 + 3 * i]), hi = int.Parse(data[2 + 3 * i]), b = int.Parse(data[3 + 3 * i]); // rest[x - lo]: x에서 b 이하의 작은 소수를 모두 나누어 없애고 남은 수 var rest = new int[hi - lo + 1]; for (int x = lo; x <= hi; x++) rest[x - lo] = x; foreach (int p in primes) { if (p > b) break; int first = (lo + p - 1) / p * p; // lo 이상인 첫 p의 배수(정수 나눗셈) for (int x = first; x <= hi; x += p) { int r = rest[x - lo]; while (r % p == 0) r /= p; rest[x - lo] = r; } } // 남은 수가 1이 아니면 9,000보다 큰 소수 하나이거나, b보다 큰 소수들의 곱이다 int count = 0, smallest = 0, largest = 0; for (int x = lo; x <= hi; x++) { if (rest[x - lo] <= b) { if (count == 0) smallest = x; largest = x; count++; } } if (count > 0) output.Append(count).Append(' ').Append(smallest).Append(' ').Append(largest).Append('\n'); else output.Append("0\n"); } Console.Write(output); }}
C++main.cpp · 52 行
#include <iostream>#include <numeric>#include <vector>using namespace std;const int ROOT = 9000; // 9000 × 9000 = 81,000,000: 이보다 큰 소수는 한 수에 많아야 한 번 들어 있다int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int q; cin >> q; // 에라토스테네스의 체로 9,000 이하의 소수를 모은다 vector<bool> composite(ROOT + 1, false); vector<int> primes; for (int i = 2; i <= ROOT; i++) { if (!composite[i]) { primes.push_back(i); for (int j = i * i; j <= ROOT; j += i) composite[j] = true; } } while (q-- > 0) { int lo, hi, b; cin >> lo >> hi >> b; // rest[x - lo]: x에서 b 이하의 작은 소수를 모두 나누어 없애고 남은 수 vector<int> rest(hi - lo + 1); iota(rest.begin(), rest.end(), lo); for (int p : primes) { if (p > b) break; int first = (lo + p - 1) / p * p; // lo 이상인 첫 p의 배수(정수 나눗셈) for (int x = first; x <= hi; x += p) { int r = rest[x - lo]; while (r % p == 0) r /= p; rest[x - lo] = r; } } // 남은 수가 1이 아니면 9,000보다 큰 소수 하나이거나, b보다 큰 소수들의 곱이다 int count = 0, smallest = 0, largest = 0; for (int x = lo; x <= hi; x++) { if (rest[x - lo] <= b) { if (count == 0) smallest = x; largest = x; count++; } } if (count > 0) cout << count << ' ' << smallest << ' ' << largest << '\n'; else cout << "0\n"; } return 0;}
Cmain.c · 49 行
#include <stdio.h>#define ROOT 9000 /* 9000 × 9000 = 81,000,000: 이보다 큰 소수는 한 수에 많아야 한 번 들어 있다 */#define SPAN 9000 /* 창 하나에 들어가는 수의 최대 개수 */static char composite[ROOT + 1];static int primes[ROOT], prime_count = 0;static int rest[SPAN];int main(void) { int q; if (scanf("%d", &q) != 1) return 1; /* 에라토스테네스의 체로 9,000 이하의 소수를 모은다 */ for (int i = 2; i <= ROOT; i++) { if (!composite[i]) { primes[prime_count++] = i; for (int j = i * i; j <= ROOT; j += i) composite[j] = 1; } } while (q-- > 0) { int lo, hi, b; scanf("%d %d %d", &lo, &hi, &b); /* rest[x - lo]: x에서 b 이하의 작은 소수를 모두 나누어 없애고 남은 수 */ for (int x = lo; x <= hi; x++) rest[x - lo] = x; for (int k = 0; k < prime_count && primes[k] <= b; k++) { int p = primes[k]; int first = (lo + p - 1) / p * p; /* lo 이상인 첫 p의 배수(정수 나눗셈) */ for (int x = first; x <= hi; x += p) { int r = rest[x - lo]; while (r % p == 0) r /= p; rest[x - lo] = r; } } /* 남은 수가 1이 아니면 9,000보다 큰 소수 하나이거나, b보다 큰 소수들의 곱이다 */ int count = 0, smallest = 0, largest = 0; for (int x = lo; x <= hi; x++) { if (rest[x - lo] <= b) { if (count == 0) smallest = x; largest = x; count++; } } if (count > 0) printf("%d %d %d\n", count, smallest, largest); else printf("0\n"); } return 0;}
Craykonmain.cray · 72 行
q = 控制台.读行().转数字();뿌리 = 9000; // 9000 × 9000 = 81,000,000: 이보다 큰 소수는 한 수에 많아야 한 번 들어 있다// 에라토스테네스의 체로 9,000 이하의 소수를 모은다소수인가 = 新列表(뿌리 + 1, 真);소수들 = [];循环 (i = 2; i <= 뿌리; i++){ 如果 (소수인가[i]) { 소수들.添加(i); 循环 (j = i * i; j <= 뿌리; j += i) { 소수인가[j] = 假; } }}循环 (i = 0; i < q; i++){ 줄 = 控制台.读数字(); lo = 줄[0]; hi = 줄[1]; b = 줄[2]; // 남은수[x - lo]: x에서 b 이하의 작은 소수를 모두 나누어 없애고 남은 수 남은수 = []; 循环 (x = lo; x <= hi; x++) { 남은수.添加(x); } 遍历 (p 在 소수들) { 如果 (p > b) { 跳出; } 첫배수 = 数学.商(lo + p - 1, p) * p; // lo 이상인 첫 p의 배수. `/`는 소수가 나오므로 몫을 쓴다 循环 (x = 첫배수; x <= hi; x += p) { r = 남은수[x - lo]; 当 (r % p == 0) { r = 数学.商(r, p); } 남은수[x - lo] = r; } } // 남은 수가 1이 아니면 9,000보다 큰 소수 하나이거나, b보다 큰 소수들의 곱이다 개수 = 0; 가장작은 = 0; 가장큰 = 0; 循环 (x = lo; x <= hi; x++) { 如果 (남은수[x - lo] <= b) { 如果 (개수 == 0) { 가장작은 = x; } 가장큰 = x; 개수 += 1; } } 如果 (개수 > 0) { 控制台.输出([개수, 가장작은, 가장큰]); } 否则 { 控制台.输出(0); }}