time limit per test
3 seconds
memory limit per test
256 megabytes
Given an array of nn positive integers a1,a2,…,ana1,a2,…,an (1≤ai≤10001≤ai≤1000). Find the maximum value of i+ji+j such that aiai and ajaj are coprime,†† or −1−1 if no such ii, jj exist.
For example consider the array [1,3,5,2,4,7,7][1,3,5,2,4,7,7]. The maximum value of i+ji+j that can be obtained is 5+75+7, since a5=4a5=4 and a7=7a7=7 are coprime.
†† Two integers pp and qq are coprime if the only positive integer that is a divisor of both of them is 11 (that is, their greatest common divisor is 11).
Input
The input consists of multiple test cases. The first line contains an integer tt (1≤t≤101≤t≤10) — the number of test cases. The description of the test cases follows.
The first line of each test case contains an integer nn (2≤n≤2⋅1052≤n≤2⋅105) — the length of the array.
The following line contains nn space-separated positive integers a1a1, a2a2,..., anan (1≤ai≤10001≤ai≤1000) — the elements of the array.
It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105.
Output
For each test case, output a single integer — the maximum value of i+ji+j such that ii and jj satisfy the condition that aiai and ajaj are coprime, or output −1−1 in case no ii, jj satisfy the condition.
Example
Input
Copy
6
3
3 2 1
7
1 3 5 2 4 7 7
5
1 2 3 4 5
3
2 2 4
6
5 4 3 15 12 16
5
1 2 2 3 6
Output
Copy
6
12
9
-1
10
7
Note
For the first test case, we can choose i=j=3i=j=3, with sum of indices equal to 66, since 11 and 11 are coprime.
For the second test case, we can choose i=7i=7 and j=5j=5, with sum of indices equal to 7+5=127+5=12, since 77 and 44 are coprime.
每个测试的时间限制为 3 秒 每个测试的内存限制为 256 兆字节 给定一个包含 n 个正整数的数组 a1、a2、…、an（1≤ai≤1000）。求出 i+j 的最大值，使得 ai 和 aj 互质，† 如果不存在这样的 i、j，则为 −1。
例如，考虑数组 [1,3,5,2,4,7,7]。由于 a5=4 和 a7=7 互质，因此可以得到的 i+j 的最大值是 5+7。
† 如果两个整数 p 和 q 的唯一除数是 1（即它们的最大公约数是 1），则这两个整数互质。
输入 输入由多个测试用例组成。第一行包含一个整数 t（1≤t≤10），表示测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 n (2≤n≤2⋅105 ) — 数组的长度。
下一行包含 n 个空格分隔的正整数 a1 , a2 ,..., an (1≤ai≤1000 ) — 数组的元素。
保证所有测试用例的 n 之和不超过 2⋅105 。
输出 对于每个测试用例，输出一个整数 — i+j 的最大值，使得 i 和 j 满足 ai 和 aj 互质的条件，或者在没有 i , j 满足条件的情况下输出 −1 。
示例 输入副本 6 3 3 2 1 7 1 3 5 2 4 7 7 5 1 2 3 4 5 3 2 2 4 6 5 4 3 15 12 16 5 1 2 2 3 6 输出副本 6 12 9 -1 10 7 注意 对于第一个测试用例，我们可以选择 i=j=3 ，索引总和等于 6 ，因为 1 和 1 互质。
对于第二个测试用例，我们可以选择 i=7 和 j=5 ，索引总和等于 7+5=12 ，因为 7 和 4 互质。
代码：
#include
#include
#include
#include
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector
vector
for (int i = 0; i < n; ++i) {
cin >> a[i];
index[a[i]] = i + 1;
}
int max_sum = -1;
for (int i = 1; i <= 1000; ++i) {
if (index[i] == -1) continue;
for (int j = 1; j <= 1000; ++j) {
if (index[j] == -1) continue;
if (gcd(i, j) == 1) {
max_sum = max(max_sum, index[i] + index[j]);
}
}
}
cout << max_sum << endl;
}
return 0;
}