← 返回题目列表

Codeforces · 1848/E

E. 维卡和石头跳跃

中文机器翻译题面 查看原题

在维卡的家乡符拉迪沃斯托克,有一片美丽的大海。

你经常可以看到孩子们在偷石头。这是以小角度向海中扔一块石头,使其飞得很远并在水面上弹起数次的过程。

Vika 曾多次撇过石头,知道如果你以 $$$f$$$ 的力从海岸垂直于海岸线扔出一块石头,它会首先在距海岸 $$$f$$$ 的距离处接触水面,然后反弹并在距前一个接触点 $$$f - 1$$$ 的距离处再次接触水面。石头将继续沿直线飞行,减少与水接触的点之间的距离,直到落入大海。

形式上,石头接触水面的点将具有以下坐标:$$$f$$$、$$$f + (f - 1)$$$、$$$f + (f - 1) + (f - 2)$$$、...、$$$f + (f - 1) + (f - 2) + \ldots + 1$$$(假设 $$$0$$$是海岸线的坐标)。

有一次,傍晚时分,维卡沿着符拉迪沃斯托克的堤岸散步时,看到一群人在海上跳过石头,用不同的力量从同一地点将它们发射出去。

她开始感兴趣的是,最多有多少个人可以用力 $$$f_i$$$ 发射一块石头,这样所有 $$$f_i$$$ 都是不同的正整数,并且所有 $$$n$$$ 石头都在坐标 $$$x$$$ 的点接触到水面(假设 $$$0$$$ 是海岸线的坐标)。

维卡想了想,回答了她的问题。之后,她开始分析,如果她将坐标 $$$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$$$ 相乘的整数 $$$x_i$$$ 的数量。

输入的第二行包含 $$$q$$$ 整数 $$$x_1, x_2, x_3, \ldots, x_q$$$ ($$$1 \le x_i \le 10^6$$$) - 语句中描述的整数。

输出

输出 $$$q$$$ 整数,其中第 $$$i$$$ 个数字对应于 Vika 的坐标 $$$X_i$$$ 问题的答案。输出所有对 $$$M$$$ 取模的答案。

示例

输入 #1

1 2 179
2 3

输出 #1

1
2

输入 #2

7 5 998244353
2 13 1 44 179

输出 #2

2
4
4
8
16

输入 #3

1000000000 10 179
58989 49494 8799 9794 97414 141241 552545 145555 548959 774175

输出 #3

120
4
16
64
111
43
150
85
161
95

注意

在第一个示例中,要使石头在坐标为 $$$2$$$ 的点接触到水,需要用 $$$2$$$ 的力将其抛出。要使石头在坐标 $$$2 \cdot 3 = 6$$$ 的点接触到水,需要用 $$$3$$$ 或 $$$6$$$ 的力将其抛出。

在第二个示例中,您可以用 $$$5$$$ 或 $$$14$$$ 的力撇去一块石头,使其在坐标为 $$$7 \cdot 2 = 14$$$ 的点接触到水。对于坐标 $$$14 \cdot 13 = 182$$$,有 $$$4$$$ 可能的力:$$$20$$$、$$$29$$$、$$$47$$$、$$$182$$$。