題目

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