CF1834E.MEX of LCM
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given an array a of length n . A positive integer x is called good if it is impossible to find a subsegment † of the array such that the least common multiple of all its elements is equal to x .
You need to find the smallest good integer.
A subsegment † of the array a is a set of elements al,al+1,…,ar for some 1≤l≤r≤n . We will denote such subsegment as [l,r] .
输入格式
Each test consists of multiple test cases. The first line of each test case contains a single integer t ( 1≤t≤5⋅104 ) — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer n ( 1≤n≤3⋅105 ) — the length of the array a .
The second line of each test case contains n integers a1,a2,…,an ( 1≤ai≤109 ) — the elements of the array a .
It is guaranteed that the sum of n over all test cases does not exceed 3⋅105 .
输出格式
For each test case, output a single integer — the smallest good integer.
输入输出样例
输入#1
6 3 1 2 3 5 1 2 3 4 5 2 2 3 1 1000000000 12 1 8 4 2 3 5 7 2 9 10 11 13 12 7 2 5 4 2 1 1 2 3 11 8 9
输出#1
4 7 1 1 16 13
说明/提示
In the first test case, 4 is a good integer, and it is the smallest one, since the integers 1,2,3 appear in the array, which means that there are subsegments of the array of length 1 with least common multiples of 1,2,3 . However, it is impossible to find a subsegment of the array with a least common multiple equal to 4 .
In the second test case, 7 is a good integer. The integers 1,2,3,4,5 appear explicitly in the array, and the integer 6 is the least common multiple of the subsegments [2,3] and [1,3] .
In the third test case, 1 is a good integer, since the least common multiples for the integer in the subsegments [1,1],[1,2],[2,2] are 2,6,3 , respectively.