【NOI2018】屠龙勇士 排行榜


时间限制: 2 s
空间限制: 512 MB

题目描述

小D最近在网上发现了一款小游戏。游戏的规则如下:

小D觉得这款游戏十分无聊,但最快通关的玩家可以获得ION2018的参赛资格,于是小D决定写一个笨笨的机器人帮她通关这款游戏,她写的机器人遵循以下规则:

那么显然机器人的攻击次数是决定能否最快通关这款游戏的关键。小D现在得知了每条巨龙的所有属性,她想考考你,你知道应该将机器人的攻击次数 $x$ 设置为多少,才能用最少的攻击次数通关游戏吗?

当然如果无论设置成多少都无法通关游戏,输出-1即可。

输入格式

从标准输入读入数据。

第一行一个整数 $T$ ,代表数据组数。

接下来 $T$ 组数据,每组数据包含5行。

输出格式

输出到标准输出。

一共 $T$ 行。

第 $i$ 行一个整数,表示对于第 $i$ 组数据,能够使得机器人通关游戏的最小攻击次数 $x$ ,如果答案不存在,输出-1

样例

输入

输出

样例解释

第一组数据:

第二组数据:

子任务

测试点编号$n$$m$$p_ia_i攻击力其他限制
1$\le 10^5$$= 1$$= 1$$\le 10^5$$= 1$
2
3$\le 10^5$
4
5$\le 10^3$$\le 10^3$$\le 10^5$特性1、特性2
6
7
8$= 1$$= 1$$\le 10^8$$\le 10^8$\le 10^6$特性1
9
10
11
12
13
14$= 10^5$$= 10^5$$= 1$无特殊限制
15
16 $\le$ 10^5 $\le$ 10^5所有 $p_i$ 是质数$\le 10^{12}$特性1
17
18无特殊限制
19
20

特性1是指:对于任意的$i$,$a_i \le p_i$。

特性2是指:$LCM(p_i) \le 10^6$ 即所有 $p_i$ 的最小公倍数不大于 $10^6$。

对于所有的测试点, $T\le 5$ , 所有武器的攻击力 $\le 10^6$ ,所有 $p_i$ 的最小公倍数 $\le 10^{12}$ 。

提示

你所用到的中间结果可能很大,注意保存中间结果的变量类型。

题目来源

NOI 2018 Day 2


关于标准输出的说明(最后更新:2018年10月23日)

标准输出将被重定向到内存中,所以你的内存使用量也包括了你的标准输出的大小(向上取整到 4KB 的倍数)。

如果你的程序要进行大量输出,请考虑这一点。




Judge Duck Online | 评测鸭在线
Server Time: 2019-10-17 00:42:17 | Loaded in 0 ms | Server Status
个人娱乐项目,仅供学习交流使用