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

题目

暴力代码，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;
}