2025年 北马其顿编程竞赛 (Macedonian programming contests 2025)

赛事等级： 社区与地区级竞赛 (Community and Regional competition)
内容类型： 竞赛题目 (Competition tasks)

题目名称：卓科再次成为程序员 (Жучко повторно програмер)

题目描述

卓科（Жучко）厌倦了粉刷房子，决定重新报考他最喜欢的计算机科学学院。学院著名的教授埃利姆（Elim）决定向卓科证明，粉刷房子对他来说其实是一份更合适的工作。教授给了卓科一个包含 $N$ 个数字的数组 $A$。

随后，教授向他提出了 $Q$ 个与该数组相关的问题。

教授所有的提问形式都相同，由三个整数 $L$、$R$ 和 $X$ 表示。问题的核心是：最少需要将数字 $X$ 增加或减少多少次（每次 $1$ 个单位），才能使得到的新数字同时满足以下两个条件：

1. 该数字是一个质数。
2. 该数字是数组 $A$ 中从第 $L$ 个位置到第 $R$ 个位置（区间 $[L, R]$）内至少一个数字的因数。

卓科听完题目后，立刻丧失了信心，灰溜溜地回去粉刷房子了。如果你决定报考这所名牌学院，你需要编写一个程序来回答所有这 $Q$ 个问题。

输入格式

• 第一行包含两个整数 $N$ 和 $Q$ ($1 \le N \le 1,000,000$，$1 \le Q \le 100,000$)，分别表示数组 $A$ 的元素个数和教授提出的问题数量。
• 第二行包含 $N$ 个整数，代表数组 $A$ 的元素 $A_i$ ($2 \le A_i \le 1,000,000$)。
• 接下来的 $Q$ 行，每行包含三个整数 $L_i, R_i, X_i$ ($1 \le L_i \le R_i \le N$ 且 $1 \le X_i \le 1,000,000$)，描述第 $i$ 个问题。

评分说明：

• 30% 的分数满足：$N, Q \le 1,000$。
• 另有 20% 的分数满足：$N, Q \le 20,000$。
• 另有 30% 的分数满足：$N \le 200,000$。

输出格式

• 输出 $Q$ 行，每行包含一个整数，即对应问题的答案。

限制条件

• 时间限制： 1.0 秒
• 内存限制： 128 MB

样例说明

输入：

6 3
2 7 6 10 4 21
1 3 8
2 4 4 
4 6 10

输出：

1
1
3

解析：

1. 第一个问题 (1 3 8)：$X=8$。将 $X$ 减 $1$ 得到 $7$。$7$ 是质数，且是 $A[2]$（即 $7$）的因数。步数为 $1$。
2. 第二个问题 (2 4 4)：$X=4$。将 $X$ 加 $1$ 得到 $5$。$5$ 是质数，且是 $A[4]$（即 $10$）的因数。步数为 $1$。
3. 第三个问题 (4 6 10)：$X=10$。将 $X$ 减 $3$ 得到 $7$。$7$ 是质数，且是 $A[6]$（即 $21$）的因数。步数为 $3$。

版权信息

• 项目： Macedonian Programming Contests 2025
• 赛事： 社区与地区级竞赛 (Community and Regional competition)
• 版权方： ZIM (北马其顿计算机科学家协会)