Bitwise Or vs LCM
链接：https://ac.nowcoder.com/acm/contest/11196/A
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld
题目描述
给你一个长度为 n 的序列 a (1<=a[i]<=10e6 )，你需要找到一个二元组 (i, j) (1 <= i < j <= n)，满足a[i]|a[j] >= lcm(a[i],a[j]) 。其中 | 代表按位或，lcm 代表最小公倍数。如果无解，输出 -1。
输入描述:
第一行包含一个整数 n(1≤n≤2e5 )，代表序列的长度。
第二行包含 n 个整数 a1,a2,…an (1<=a[i]<=1e6)。
输出描述:
输出两个整数 i, j (1<= i < j <= n ) 满足a[i]|a[j] >= lcm(a[i],a[j])。 如果有多组解，你可以输出任意一组；如果无解，输出 -1。
示例1
输入
2
1 1
输出
1 2
示例2
输入
2
3 4
输出
-1
说明:在样例 2 中，3 | 4 = 7 < lcm(3,4) = 12，因此无解。
本题的话看数据范围和时间限制就知道纯暴力必超时，但是我们可以简化一下循环的次数，由于这里需要求两个数的最小公倍数（两个数的乘积/两个数的最大公约数），所以要考虑 long long ，最后输出的是每个数对应的下标（从1开始）所以这里要用到结构体，如下：
struct xx
{
int x,y;
}a[N];bool cmp(xx a,xx b)
{
return a.x<b.x;
}
然后的话这里需要求两个数的LCM所以也先用函数处理一下，如下：
int lcm(int a, int b)
{
return a/__gcd(a,b)*b;
}
接下来就比较简单了，直接两层循环，暴力找就行，这里最后特判一下，如果循环超过 1e6 直接输出 -1 然后结束就行（之前某佬给我说的，反正如果这样的题，超时的话就加上这个条件，挺好用的）下面是完整代码给大家参考：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
struct xx
{
int x,y;
}a[N];
bool cmp(xx a,xx b)
{
return a.x<b.x;
}
int lcm(int a, int b)
{
return a/__gcd(a,b)*b;
}
signed main()
{
int n;cin>>n;for(int i=1;i<=n;i++){
cin>>a[i].x;a[i].y=i;}sort(a+1,a+n+1,cmp);int ans=0;for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
ans++;if((a[i].x|a[j].x)>=lc(a[i].x,a[j].x)){
cout<<min(a[i].y,a[j].y)<<" "<<max(a[j].y,a[i].y)<<endl;return 0;}}if(ans>=1000000){
cout<<"-1"<<endl;return 0;}}cout<<"-1"<<endl;return 0;
}
本篇到这里就结束了，如果有什么疑问，或者对本篇博客有什么改进意见的话，欢迎评论留言，你们的意见就是我进步的动力~