P17735 [ICPC 2019 Xuzhou R] Multiply

阿尔杜梅拉和贝赫拉都喜欢大数、大量的数以及大量的大数。他们也喜欢对这些数进行计算。 一天，阿尔杜梅拉写下了 $N$ 个正整数 $a_1, a_2,\cdots, a_N$。他决定通过对每个数施加阶乘使它们变大，于是这些数变成了 $a_1!, a_2!,\cdots, a_N!$。最后，他将所有 $N$ 个数相乘，得到一个超大数 $Z=a_1!\times a_2!\times\cdots\times a_N!$。 几天后，贝赫拉遇见了阿尔杜梅拉，贝赫拉告诉阿尔杜梅拉他想出了另外两个数 $X,Y$。于是，他们开始不断将 $Z$ 乘以 $X$，生成序列 $b_i=Z\times X^i$，以找出使得 $b_i$ 是 $Y!$ 的因子的最大的 $i$ 值。 作为阿尔杜梅拉和贝赫拉的朋友，你意识到这是一个极其耗时的过程。因此，为了节省时间，你决定编写一个程序来计算答案。

第一行包含一个正整数 $T$ ($T\leq 8$) —— 测试用例的数量。 每个测试用例的描述包含两行：第一行包含三个正整数 $N, X, Y$ ($N\leq 10^5; 2\leq X,Y\leq 10^{18}$)，第二行包含 $N$ 个正整数 $a_1, a_2,\cdots a_N$ ($a_i \leq 10^{18}; a_1+a_2+\cdots+a_N

对于每个测试用例，输出一行一个整数，表示使得 $b_i$ 是 $Y!$ 的因子的最大的 $i$ 值。

翻译由 DeepSeek V4 Pro 完成