连乘问题

题目描述

给定 $n$ 个整数 $a_1, a_2, \cdots, a_n$，请计算一组乘积，记为 $P_1, P_2, \cdots, P_n$，其中 $P_i$ 的定义如下：

$$P_i = \frac{a_1 \cdot a_2 \cdot a_3 \cdots a_n}{a_i}$$

也就是说，$P_i$ 是 $a_1$ 到 $a_n$ 的连乘再除去 $a_i$。由于答案可能比较大，输出每个 $P_i$ 模 $10000$ 的余数。

输入格式

• 第一行：单个整数表示 $n$；

• 第二行：$n$ 个整数表示 $a_1, a_2, \cdots, a_n$。

输出格式

共 $n$ 行：第 $i$ 行输出 $P_i$ 模 $10000$ 的余数。

样例输入 #1

4
1 3 4 6

样例输出 #1

72
24
18
12

数据范围

• 对于 $30\%$ 的数据，$2 \leq n \leq 1000$；

• 对于 $60\%$ 的数据，$2 \leq n \leq 10000$；

• 对于 $100\%$ 的数据，$2 \leq n \leq 100000$，$1 \leq a_i \leq 10000$。

知识点与难度

本题涉及的知识点从属于 GESP 4级，难度等级：⭐⭐⭐。

⚠️ GESP X 级 和 星级 不得凭印象填！ 必先读 03-gesp.md，以第三步「定级」结果填 X，以第五步「定难」结果填星级。 二者均自 03-gesp.md 来，非 AI 自由发挥。

---

测试点分布

Subtask	分值	测试点编号	说明
0	10	1~2	样例 / 小规模补充样例
1	20	3~8	小规模 N≤10 / 特殊: 全1 / 特殊: 全10000 / 特殊: N=2最小
2	15	9~11	Hack: 积为0模10000 / Hack: 含10000因子 / Hack: 大数模运算
3	30	12~20	中规模 N≈1000~10000 / 大规模 N≈1e5 压力
4	25	21~25	随机 N=2~1e5 回归