题解 CF2164B Even Modulo Pair

给定长度为

n

的严格单调递增序列

a

，求是否存在一对

(x,y)

，使得：

$x<y$ ；
$x,y\in a$ ；
$y\bmod x\equiv 0\pmod 2$ 。

如果存在，给出任意一对。

数据范围：多测，

\sum n\le 10^5

，

a_i\le 10^9

。

做法

需要注意力。真注意不到。

若无解，

首先最多只能有一个偶数，因为偶数模偶数显然一定为偶数。
对于奇数，设数列里有一奇数 $a_i$ ，则若要另外的奇数 $a_j$ 模 $a_i$ 不为偶数，则其必然要在 $[2ka_i,2(k+1)a_i](k\in \mathbb{Z})$ 中。所以最多只能构造出 $\log V$ 个两两之间不符合要求的奇数。

发现

V

只有

10^9

，去重后取前

40

个（若不足则取全部）暴力枚举即可。

代码

CPP

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<fstream>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#define ll long long
#define lf double
#define ld long double
using namespace std;
ll T,n,a[200010];
int main(){
	ios::sync_with_stdio(0);
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=0;i<n;i++){
			cin>>a[i];
		}
		n=min(n,40ll);
		bool flg=0;
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				if(a[j]%a[i]%2==0){
					cout<<a[i]<<' '<<a[j]<<endl;
					flg=1;
					break;
				}
			}
			if(flg){
				break;
			}
		}
		if(!flg){
			cout<<-1<<endl;
		}
	}
	return 0;
}

题解 CF2164B Even Modulo Pair

文章操作

题解 CF2164B Even Modulo Pair

做法

相关推荐

评论

题解 CF2164B Even Modulo Pair