AcWing 4970. 公因数匹配
原题链接
困难
作者:
YMYS
,
2024-04-04 12:15:44
,
所有人可见
,
阅读 34
暴力思想。十个数据过六个,我很满足了
//2024.4.3
//https://www.acwing.com/problem/content/description/4973/
//4970.公因数匹配
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
using namespace __gnu_cxx;
using ll = long long;
const int N = 1e5+10;
int n;
int a[N];
int gcd(int a, int b){
return b ? gcd(b, a % b) : a;
}
int main()
{
#ifdef ABC
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
#endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
for(int i=0;i<n;i++) cin>>a[i];
//双指针打暴力
int i,j;
for(i=0;i<n-1;i++){
j = i+1;
while (j<n && gcd(a[i], a[j]) <= 1) j++;//注意:这里的while如果退出了,则要么j超过了界限,要么找到了有公因数的数
if(j<n) break;
}
cout<<i+1<<" "<<j+1<<endl;
return 0;
}