🇧🇬 保加利亚国家信息学奥林匹克竞赛 (NOI)

第 41 届区域赛 (Regional Round)

日期： 2025年2月9日

组别： E组（4-5年级）

题目 E2. 乘积 (PRODUCT)T2

• 时间限制： 0.5 秒
• 内存限制： 2.0 MB
• 题目作者： Emil Kelevedzhiev (Емил Келеведжиев)

题目描述

考虑闭区间 $[a_1, a_2]$ 之间的所有正整数。我们对这些数字的某些性质感兴趣，特别是与它们的整除性以及质因数分解相关的性质。

请编写程序 product，统计在给定区间内有多少个数字满足以下四种特定的性质。

输入格式

• 从标准输入读取两个正整数 $a_1$ 和 $a_2$，中间用空格分隔。

输出格式

• 在标准输出中打印 4 行，每行包含一个整数，分别对应以下统计结果：

1. 第一行： 能被 2 或 3 整除的数字个数。
2. 第二行： 质数（Prime numbers）的个数。
3. 第三行： 恰好是两个不同质数之积的数字个数（例如 $6 = 2 \times 3$）。
4. 第四行： 由 3 个或 4 个质数相乘得到的数字个数（这些质数不一定互不相同，例如 $8 = 2 \times 2 \times 2$ 或 $12 = 2 \times 2 \times 3$）。

数据范围与限制

• $2 \le a_1 \le a_2 < 5,000,000$
• 区间跨度较小：$0 \le a_2 - a_1 \le 500$
• 评分： 每个正确输出的数字都将获得该测试点的部分分数。

样例分析

样例 1

• 输入： 2 10
• 输出：

7
4
2
1

• 解释：
• 能被 2 或 3 整除：2, 3, 4, 6, 8, 9, 10（共 7 个）。
• 质数：2, 3, 5, 7（共 4 个）。
• 两个不同质数之积：6 (2×3), 10 (2×5)（共 2 个）。
• 3 或 4 个质数之积：8 (2×2×2)（共 1 个）。

样例 2

• 输入： 11 16
• 输出：

4
2
2
2

• 解释：
• 能被 2 或 3 整除：12, 14, 15, 16（共 4 个）。
• 质数：11, 13（共 2 个）。
• 两个不同质数之积：14 (2×7), 15 (3×5)（共 2 个）。
• 3 或 4 个质数之积：12 (2×2×3), 16 (2×2×2×2)（共 2 个）。

💡 解题思路

尽管 $a_2$ 的上限很大（500万），但区间长度极其短（最多只有 501 个数）。这意味着我们可以对区间内的每一个数进行单独处理。

1. 整除性检查： 直接判断 n % 2 == 0 || n % 3 == 0。
2. 质因数分解： 对于区间内的每个数 $n$，执行质因数分解：

• 统计不同质因数的个数。
• 统计总的质因数个数（计入重复项）。

3. 判定：

• 如果总质因数个数为 1，则该数为质数。
• 如果总质因数个数为 2 且两个质数不同，满足第三个条件。
• 如果总质因数个数为 3 或 4，满足第四个条件。

由于 $a_2$ 较大，建议预先使用 埃氏筛 (Sieve of Eratosthenes) 筛选出直到 $\sqrt{5,000,000} \approx 2236$ 的质数，或者直接对每个数进行分解。