22.10.14 codeforce D

题目D. Coprime

给定n个正整数数组a1,a2，…，an(1≤ai≤1000)。求i+j的最大值，使ai和aj为互素，†或−1(如果不存在i, j)。
例如，考虑数组[1,3,5,2,4,7,7]。i+j可以得到的最大值是5+7，因为a5=4和a7=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是互素的条件，或输出−1，如果i和j不满足条件。

样例

input

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

6
12
9
－1
10
7

请注意
对于第一个测试用例，我们可以选择i=j=3，指标的和等于6，因为1和1是互素。
对于第二个测试用例，我们可以选择i=7和j=5，指标之和等于7+5=12，因为7和4是互素。

#include <bits/stdc++.h>
using namespace std;

#define int long long

int a[200010];
int st[1010];
vector<vector<int> > o(1010,vector<int>(1010,0));
int pos[1010];

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	for(int i=1;i<=1001;i++)
	{
		for(int j=1;j<=i;j++)
		{
			if(__gcd(i,j)==1)
			{
				o[i].push_back(j);
				o[j].push_back(i);//预处理，保存与其互质的数
			}
		}
	}
	while(t--)
	{
		int n;
		cin>>n;
		memset(pos,-1,sizeof pos);
		
		for(int i = 1;i <= n;i ++)
		{
			cin>>a[i];
			pos[a[i]]=max(pos[a[i]],i);//保存最后一个出现的位置
		}
		int ans=0;
		bool flag = false;
		for(int i = 1;i <= n;i ++)
		{
			for(auto x:o[a[i]])
			{
				if(pos[x] != -1&&flag == false) flag = true;
				ans = max(ans, pos[x] + i);
			}
		}
		if(flag) cout<<ans<<endl;
		else cout<<-1<<endl;
	}
}```

原文地址：http://www.cnblogs.com/dyb666/p/16790243.html