【公因数匹配——暴力、（质）因数分解、哈希】

题目

暴力代码，Acwing 8/10，官网AC

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
vector<int> nums[N];
int main()
{ios::sync_with_stdio(0);cin.tie(0);int n;cin >> n;for(int i = 1; i <= n; i++){int x;cin >> x;for(int j = 2; j <= x / j; j++){if(x % j == 0) nums[j].push_back(i), nums[x / j].push_back(i);}if(x > 1) nums[x].push_back(i);}int ansi = 1e9, ansj = 1e9;for(auto &num : nums){for(auto &i : num)for(auto &j : num){if(i < j && (i < ansi || i == ansi && j < ansj)){ansi = i;ansj = j;}}}cout << ansi << ' ' << ansj;
}

代码

#pragma GCC optimize(3)#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
unordered_map<int, int> mp;
int ansi = 1e9, ansj = 1e9;
void check(int x, int i) //优化：先记录（所有的结果）再匹配改为边记录（最早的结果）边匹配
{if(mp.count(x)){if(mp[x] < ansi) {ansi = mp[x];ansj = i;}}else mp[x] = i;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);int n;cin >> n;for(int i = 1; i <= n; i++){int x;cin >> x;for(int j = 2; j <= x / j; j++) //优化：普通的因数分解改为质数分解{if(x % j == 0){check(j, i); //if(x / j != j) check(x / j, i);while(x % j == 0) x /= j;}}if(x > 1) check(x, i);}cout << ansi << ' ' << ansj;
}