题目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;
}
}```
标签:14,int,pos,22.10,ai,测试用例,互素,codeforce,1010
From: https://www.cnblogs.com/dyb666/p/16790243.html