Codeforces Round 827 (Div. 4) D 1e5+双重for循环技巧

这篇具有很好参考价值的文章主要介绍了Codeforces Round 827 (Div. 4) D 1e5+双重for循环技巧。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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。

Codeforces Round 827 (Div. 4) D 1e5+双重for循环技巧,算法,c++

**注**

对于第一个测试案例,我们可以选择指数之和等于 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

// 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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Educational Codeforces Round 62 (Rated for Div. 2) C. Playlist

     一开始肯定要排个序,b相同时t大的在前边,不同时b大的在前面。 然后想最多只能选k个的限制,可以这样想,每次用到的b只能用已选到的最小的值,那可以把每个b都枚举一遍,然后每一次选时长最长的,且b大于等于当前的b的那k个不就好了吗,时间复杂度也才O(n),然

    2024年02月12日
    浏览(39)
  • Educational Codeforces Round 154 (Rated for Div. 2)(A—C)

    从1到9,每个数后面都可以加一个数构成一个含有两个数的质数,只需要从s[1]~s[9]中找到一个数与s[0]构成质数即可 观察样例即可发现两个字符串只要在相同位置都有 01 存在就能成功实现转换后两个字符串相等 可以先假设字符串是可以成立的,那么接下来就判断它什么时间是

    2024年02月10日
    浏览(38)
  • Educational Codeforces Round 154 (Rated for Div. 2)(A—D)

    从1到9,每个数后面都可以加一个数构成一个含有两个数的质数,只需要从s[1]~s[9]中找到一个数与s[0]构成质数即可 观察样例即可发现两个字符串只要在相同位置都有 01 存在就能成功实现转换后两个字符串相等 可以先假设字符串是可以成立的,那么接下来就判断它什么时间是

    2024年02月10日
    浏览(34)
  • Educational Codeforces Round 135 (Rated for Div. 2)C. Digital Logarithm(思维)

    C. Digital Logarithm 给两个长度位 n n n 的数组 a a a 、 b b b ,一个操作 f f f 定义操作 f f f 为, a [ i ] = f ( a [ i ] ) = a [ i ] a[i]=f(a[i])=a[i] a [ i ] = f ( a [ i ]) = a [ i ] 的位数 求最少多少次操作可以使 a 、 b a、b a 、 b 两个数组变得完全相同 性质: 对于任何数,经过两次操作我们一定可以

    2024年02月20日
    浏览(37)
  • 【每日一题】—— B. Ternary String (Educational Codeforces Round 87 (Rated for Div. 2))

    🌏博客主页: PH_modest的博客主页 🚩当前专栏: 每日一题 💌其他专栏: 🔴 每日反刍 🟡 C++跬步积累 🟢 C语言跬步积累 🌈座右铭: 广积粮,缓称王! 题目大意:给你一串由1、2、3组成的数组,让你求一个最短的子串,要求这个子串包含1、2、3 题目链接:B. Ternary String

    2024年02月16日
    浏览(35)
  • Educational Codeforces Round 157 (Rated for Div. 2) F. Fancy Arrays(容斥+组合数学)

    题目 称一个长为n的数列a是fancy的,当且仅当: 1. 数组内至少有一个元素在[x,x+k-1]之间 2. 相邻项的差的绝对值不超过k,即 t(t=50)组样例,每次给定n(1=n=1e9),x(1=x=40), 求fancy的数组的数量,答案对1e9+7取模 思路来源 灵茶山艾府群 官方题解 题解 看到 至少 的字眼,首先想到容斥,

    2024年02月05日
    浏览(38)
  • Educational Codeforces Round 161 (Rated for Div. 2) E. Increasing Subsequences 动态规划逼近,二进制拆分补充,注意严格递增

    Problem - E - Codeforces 目录 推荐视频: 题意: 细节(我踩得没什么价值的坑): 思路: 对样例3 (X = 13)做解释: —————— 总思路: —————— 动态规划逼近: —————— 二进制拆分补充剩余: 核心代码:  E_哔哩哔哩_bilibili 其实有一些细节说的不是特别清楚好

    2024年02月22日
    浏览(38)
  • Educational Codeforces Round 161 (Rated for Div. 2) E题 动态规划逼近,二进制拆分补充,注意严格递增strictly increasing

    Problem - E - Codeforces 目录 推荐视频: 题意: 细节(我踩得没什么价值的坑): 思路: 对样例3 (X = 13)做解释: —————— 总思路: —————— 动态规划逼近: —————— 二进制拆分补充剩余: 核心代码:  E_哔哩哔哩_bilibili 其实有一些细节说的不是特别清楚好

    2024年01月24日
    浏览(42)
  • Codeforces Round 866 (Div. 2)

    给出一个仅由_或^组成的字符串,你可以在任意位置添加_或^字符,使得字符串满足: 任意字符要么属于^_^的一部分,要么属于^^的一部分。求最少添加的字符数量。 对于_我们只需处理没有组成^_^的_: ①如果_在首位置且左边没有^则添加^ ②如果_在尾位置且右边没有^则添加

    2023年04月25日
    浏览(54)
  • Codeforces Round 926 (Div. 2)

    类似于倍投法,就是在一赔一的情况下,第一次压一块钱,每输一次就押注上一次两倍的金额. 假如资金无限的话,这种方法赢的期望为无穷大.原理类似于二进制,不论你输再多次,只要赢一次总额就增加了1.比如 15 二进制1111,前3把一直输,但是只要第4把赢,就一定可以增加 1

    2024年02月20日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包