给定一个由 n 个正整数 a1,a2,…,an ( 1≤ai≤1000 ) 组成的数组。求 i+j 的最大值，使得 ai 和 aj 互素，如果不存在这样的i,j则输出-1
例如，考虑数组 [1,3,5,2,4,7,7]，i+j 可以得到的最大值是 5+7 ，因为 a5=4 和 a7=7 是互素的。
如果两个整数 p 和 q 的唯一被除数是 1 (即它们的最大公约数是 1 )，那么这两个整数 p 和 q 是互素的。
3155: 互素
时间限制: 3 Sec 内存限制: 128 MB提交: 0 解决: 49
[提交][状态][讨论版][命题人:]
题目描述
输入描述
输入由多个测试用例组成。第一行包含一个整数 t ( 1≤t≤10) - 测试用例的数量。测试用例说明如下。
每个测试用例的第一行都包含一个整数 n( 2≤n≤2⋅105) - 数组的长度。
下一行包含 n个空格分隔的正整数 a1 , a2 ,..., an ( 1≤ai≤1000) - 数组元素。
保证所有测试用例中 n的总和不超过 2⋅105 。
每个测试用例的第一行都包含一个整数 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 是素数。
来源
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
cnt: 11102
关于网站改版