首页 > 其他分享 >22.10.14 codeforce D

22.10.14 codeforce D

时间:2022-10-14 01:45:33浏览次数:65  
标签:14 int pos 22.10 ai 测试用例 互素 codeforce 1010

题目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

相关文章

  • Codeforces Round #827 (Div. 4) A - G
    A.Sumvoidsolve(){inta[3]={};cin>>a[0]>>a[1]>>a[2];sort(a,a+3);if(a[2]==a[0]+a[1])cout<<"YES\n";elsecout<<"NO......
  • WEB自动化-14-Cypress 其他
    14其他14.1IDE集成  有非常多的三方插件都支持集成IDE中,从而提高工作效率,我们以VisualStudioCode为例讲解。主要插件如下所示:CypressFixture-IntelliSense......
  • 进入python的世界_day14_python基础——算法、三元表达式、生成式、匿名函数
    一、算法1.介绍​ 算法是通过数学模型运算得到某些数据的过程,在python中通过与代码相结合,可以在特定场景下很方便的解决问题2.应用场景​ 很广,大数据推广就是利用算......
  • Python学习路程——Day14
    Python学习路程——Day14算法简介1、什么是算法''' 算法就是解决问题的有效方法,并不是所有的算法都很高效、也不是所有的算法都合格。'''2、算法应用场景''' 推荐......
  • 141. 环形链表
    题目描述给你一个链表的头节点head,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪next指针再次到达,则链表中存在环。为了表示给定链表中的环,评测系统内......
  • Codeforces Round #780 D
    D.MaximumProductStrikesBack显然我们是不喜欢0的我们可以对0进行切割分成若干段然后我们要是是段数内乘积为负数显然我们也是不喜欢的我们必须要砍掉一个负数......
  • Codeforces Round #763 C
    C.BalancedStoneHeaps最小值最大显然二分考虑check首先我们从前往后做的话要考虑后面的消息显然不可取我们考虑从后往前做但是这里要注意的只有一点就是我们从......
  • 11.14/11.15 Apache和PHP结合 11.16/11.17 Apache默认虚拟主机
    11.14/11.15Apache和PHP结合修改Apache(httpd)主配置文件定义ServerName以消除Apache启动时所产生的警告未修改前[root@linux-5~]#/usr/local/apache2.4/bin/apachect......
  • JavaWeb学习日记2022.10.13
    排序查询(P13)/*排序查询SELECT字段列表FROM表名ORDERBY排序字段名1[排序方式1],排序字段名2[排序方式2]...;排序方式ASC:升序排列(默认值)DESC:降序排列*/--1......
  • P1434
    [SHOI2002]滑雪题目描述Michael喜欢滑雪。这并不奇怪,因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来......