CF1848E Vika and Stone Skipping

在 Vika 的家乡符拉迪沃斯托克，有一片美丽的海。 你经常可以看到孩子们在打水漂。这是指以一个较小的角度将石头扔向海面，使其飞得很远并在水面上弹跳多次的过程。 Vika 已经打过很多次水漂，并且知道如果你以力度 $f$ 从岸边垂直于海岸线扔出一块石头，它第一次接触水面的距离是离岸 $f$ 的位置，然后弹起后再次接触水面的距离是从上一个接触点起 $f-1$ 的位置。石头会继续沿直线飞行，每次接触水面的距离依次减少，直到落入海中。 形式化地说，石头接触水面的各点坐标依次为：$f$，$f + (f-1)$，$f + (f-1) + (f-2)$，……，$f + (f-1) + (f-2) + \ldots + 1$（假设 $0$ 是岸线的坐标）。 有一次，Vika 傍晚在符拉迪沃斯托克的堤岸散步时，看到一群男孩在同一个点用不同的力度打水漂。 她对此产生了兴趣：最多有多少个男孩可以用各自的力度 $f_i$ 扔石头，使得所有 $f_i$ 都是不同的正整数，并且所有 $n$ 块石头都恰好在坐标 $x$ 的位置接触水面（假设 $0$ 是岸线的坐标）。 Vika 想了一会儿，得出了她的问题的答案。之后，她又开始分析，如果将坐标 $x$ 依次乘以一些正整数 $x_1$、$x_2$、……、$x_q$，她挑选这些数来进行分析，答案会如何变化。 Vika 觉得自己难以独立完成这样的分析，于是向你寻求帮助。 形式化地说，Vika 关心的问题是关于坐标 $X_1 = x \cdot x_1$，$X_2 = X_1 \cdot x_2$，……，$X_q = X_{q-1} \cdot x_q$ 的答案。由于这些坐标的答案可能很大，请你对 $M$ 取模输出。保证 $M$ 是质数。

输入的第一行包含三个整数 $x$（$1 \le x \le 10^9$）、$q$（$1 \le q \le 10^5$）和 $M$（$100 \le M \le 2 \cdot 10^9$）——Vika 自己解答的初始坐标、Vika 要依次乘的整数个数以及质数模数 $M$。 第二行包含 $q$ 个整数 $x_1, x_2, x_3, \ldots, x_q$（$1 \le x_i \le 10^6$）——题目描述中的这些整数。

输出 $q$ 个整数，第 $i$ 个数表示对于坐标 $X_i$，Vika 问题的答案。所有答案都对 $M$ 取模。

在第一个样例中，要让石头在坐标 $2$ 处接触水面，需要以力度 $2$ 扔出石头。要让石头在坐标 $2 \cdot 3 = 6$ 处接触水面，需要以力度 $3$ 或 $6$ 扔出石头。 在第二个样例中，可以以力度 $5$ 或 $14$ 扔石头，使其在坐标 $7 \cdot 2 = 14$ 处接触水面。对于坐标 $14 \cdot 13 = 182$，有 $4$ 种可能的力度：$20$、$29$、$47$、$182$。 由 ChatGPT 4.1 翻译