33OJ
登录 注册

#P17735. [ICPC 2019 Xuzhou R] Multiply

[ICPC 2019 Xuzhou R] Multiply

题目描述

阿尔杜梅拉和贝赫拉都喜欢大数、大量的数以及大量的大数。他们也喜欢对这些数进行计算。

一天,阿尔杜梅拉写下了 NN 个正整数 a1,a2,⋯ ,aNa_1, a_2,\cdots, a_N。他决定通过对每个数施加阶乘使它们变大,于是这些数变成了 a1!,a2!,⋯ ,aN!a_1!, a_2!,\cdots, a_N!。最后,他将所有 NN 个数相乘,得到一个超大数 Z=a1!×a2!×⋯×aN!Z=a_1!\times a_2!\times\cdots\times a_N!。

几天后,贝赫拉遇见了阿尔杜梅拉,贝赫拉告诉阿尔杜梅拉他想出了另外两个数 X,YX,Y。于是,他们开始不断将 ZZ 乘以 XX,生成序列 bi=Z×Xib_i=Z\times X^i,以找出使得 bib_i 是 Y!Y! 的因子的最大的 ii 值。

作为阿尔杜梅拉和贝赫拉的朋友,你意识到这是一个极其耗时的过程。因此,为了节省时间,你决定编写一个程序来计算答案。

输入格式

第一行包含一个正整数 TT (T≤8T\leq 8) —— 测试用例的数量。

每个测试用例的描述包含两行:第一行包含三个正整数 N,X,YN, X, Y (N≤105;2≤X,Y≤1018N\leq 10^5; 2\leq X,Y\leq 10^{18}),第二行包含 NN 个正整数 a1,a2,⋯aNa_1, a_2,\cdots a_N (ai≤1018;a1+a2+⋯+aN<Ya_i \leq 10^{18}; a_1+a_2+\cdots+a_N<Y)。它们的含义如上所述。

输出格式

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

2
3 10 10
2 3 4
2 2 10
1 1
2
8

提示

翻译由 DeepSeek V4 Pro 完成