Codeforces Round 827 (Div. 4) D
题目链接:
https://codeforces.com/contest/1742/problem/D
给定一个由 n个正整数 a1,a2,…,an(1≤ai≤1000)组成的数组。求i+j的最大值,使得ai和aj共质,否则−1,如果不存在这样的i,j。
例如,考虑数组 [1,3,5,2,4,7,7]。由于a5=4和a7=7是共素数,所以能得到的i+j的最大值是5+7。
如果两个整数 p 和 q 的唯一被除数是 1 (即它们的【最大公约数】那么这两个整数 p 和 q 是【共素数】
**输入**
输入由多个测试用例组成。第一行包含一个整数 t(1< t <10)--测试用例的数量。测试用例说明如下。
每个测试用例的第一行包含一个整数 $n$(2 < n ,q < 2*10^5)--数组的长度。
下一行包含 n个空格分隔的正整数 a_1, a_2,..., a_n(1<a_i <1000)--数组的元素。
保证所有测试用例的 n之和不超过 2*10^5。
**输出**
对于每个测试案例,输出一个整数 i + j的最大值,使得i和j满足a_i和a_j是共素数的条件,或者在没有i、j满足条件的情况下输出-1。
**注**
对于第一个测试案例,我们可以选择指数之和等于 6的 i = j = 3,因为 1和 1是共素数。
对于第二种检验情况,我们可以选择 i = 7和 j = 5,指数之和等于 7 + 5 = 12,因为 7和 4是共素数。
思想:双重遍历n肯定会超时,除了二分,我们考虑遍历ai,ai的范围是1000,考虑ai是否存在,然后进行计算。文章来源:https://www.toymoban.com/news/detail-707698.html
代码:文章来源地址https://www.toymoban.com/news/detail-707698.html
// Problem: D. Coprime
// Contest: Codeforces - Codeforces Round 827 (Div. 4)
// URL: https://codeforces.com/contest/1742/problem/D
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+5;
int gcd(int x,int y){
if(y==0) return x;
return gcd(y,x%y);
}
int main(){
int T;
cin>>T;
while(T--){
int n;
cin>>n;
int a[N];
map<int,int> mp;
for(int i=1;i<=n;i++){
cin>>a[i];
mp[a[i]]=i;
}
int maxv=0;
for(int i=1;i<=1000;i++){
if(!mp[i]) continue;
for(int j=1;j<=1000;j++){
if(!mp[j]) continue;
if(gcd(i,j)==1){
maxv=max(maxv,mp[i]+mp[j]);
}
}
}
if(maxv==0) cout<<"-1\n";
else cout<<maxv<<"\n";
}
return 0;
}
到了这里,关于Codeforces Round 827 (Div. 4) D 1e5+双重for循环技巧的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!