题解 CF2164B Even Modulo Pair

JuRuoOIer · 2025-11-25 08:43:25 · 题解

题解 CF2164B Even Modulo Pair

其他题

给定长度为 n 的严格单调递增序列 a，求是否存在一对 (x,y)，使得：

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

数据范围：多测，\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 个（若不足则取全部）暴力枚举即可。

:::success[代码]

#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;
}

:::