题目来自DOPCPP：
公因数：一个能同时整数若干整数的整数。
暴力代码（超时）：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+10;int n;
int arr[N];signed main(){cin >> n;for(int i = 1 ;i <= n; i++) cin >> arr[i];//s表示方案中的起点 e表示终点//题目中说了 i < j for(int i = 1; i <= n-1; i++){for(int j = i+1; j <= n; j++){//公因数：能同时整除若干整数的整数if(__gcd(arr[i], arr[j]) > 1){//更新答案cout << i << " " << j << endl;return 0;}}}return 0;
}优化思路：
①找出每个数的公因数，存到map容器中。
②在枚举map容器中的公因数，找到每个公因数存的最小值，前两个就是i 和 j。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+10;int n;
int arr[N];
//用来记录哪些书可以整除An
map<int, vector<int>>q;//x表示枚举的An cnt表示在数组中的位置
void find(int x, int cnt){for(int i = 2; i<= x / i; i++){if(x % i != 0)continue;q[i].push_back(cnt);//去除重复的 iwhile(x % i == 0){x = x / i;}}//只被本身整除if(x > 1){q[x].push_back(cnt);}return;
}signed main(){cin >> n;for(int i = 1; i <= n; i++){int x; cin >> x;//记录x可以被哪些数字整除find(x, i);}//答案int s=1e7, e = 1e7;//取出容器q中元素//x表示被这个数整除 y表示在数组中位置for(auto [x, y]: q){if(y.size() < 2)continue;// 1={1，3}// 2={1，2}//我们s,e先选择1,3 然后在下一组y[0] == s时候，可以更新e的最小值了//如果第一组的y[0]小于第二组的，我们的e不应该更新//我们s、e应该选择拥有相同公因数的最小值if(y[0] < s ||(y[0] == s && y[1] < e)){//前面两个数字最小s = y[0];e = y[1];}}cout << s << " " << e << endl;return 0;
}