Bài G - Codeforces Round #552 (Div.3)

Đề bài: Cho một mảng a gồm n phần tử a(1),a(2),...,a(n). Tìm các cặp chỉ số (i,j) (1<=i<j<=n) thỏa mãn lcm(a(i),a(j)) nhỏ nhất có thể.
Đầu vào:
+ Dòng đầu tiên chứa số nguyên n (2<=n<=10^6). Số lượng phần tử của a.
+ Dòng thứ hai chứa n số nguyên a(1),a(2),...,a(n).
Đầu ra:
+ In ra hai số nguyên i,j (1<=i<j<=n) thỏa mãn lcm(a(i),a(j)) là nhỏ nhất trong số các cặp (i,j). Nếu có nhiều đáp án, in ra bất kỳ.
Ví dụ:
5
2 4 8 3 6
In ra: 1 2
Hướng dẫn:
Tôi đã nghe có rất nhiều solutions dễ với độ phức tạp O(alog(a)), với a là giá trị nhỏ nhất của a(i), nhưng tôi sẽ mô tả thuật toán với độ phức tạp O(nd), với d là số lượng ước lớn nhất của a(i).
Một cận trên tốt xấp xỉ số ước của x là $\sqrt[3]{x}$ vì vậy tôi làm việc với $O(n\sqrt[3]{x})$.
Đầu tiên, chúng ta hãy nói về ý tưởng của bài này. Ý tưởng chính là mỗi số chạy từ 1 đến 10^7, chúng ta muốn tìm hai số nhỏ nhất trong mảng mà chia hết cho số này. Sau đó chúng ta tìm câu trả lời trong số tất cả các ước này mà có ít nhất hai bội số trong mảng.
Chúng ta viết một hàm add(idx) cái mà chúng ta sẽ cố gắng thêm a(idx) đến tất cả các ước của nó. Cách dễ nhất để làm là lặp tất cả các ước với độ phức tạp O(can(idx)) và thêm nó bằng cách nào đó. Nhưng nó quá chậm. Chúng ta hãy cải tiến nó bằng một cách nào đó. Làm thế nào để chúng ta có thể bỏ qua các số không phải là ước của a(idx)? Chúng ta hãy xây dựng 1 sàn nguyên tố (Tôi rất khuyến khích với độ phức tạp O(n) vì sàn nguyên số với độ phức tạp O(nlog(n))) sẽ chậm đi gấp 2 lần), cái mà sẽ duy trì số ước tối thiểu với mỗi số từ 1 đến 10^7. Vì vậy chúng ta có thể phân tích thừa số nguyên tố với độ phức tạp (O(log(a(idx)))) và lặp tất cả các ước sử dụng đệ quy.
Và cuối cùng ta nên chú ý rằng - Lời giải này có thể TLE và yêu cầu chúng ta tối ưu hóa các ràng buộc. Tôi khuyên bạn nên sử dụng cặp số nguyên cho mỗi ước và thêm nó sử dụng một vài câu lệnh if.
Lời giải 1:

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000000+5;
long long int ans=0x3f3f3f3f3f3f3f3f;
int a[maxn],b[maxn];
int main ()
{
 int n,i,j,ansj,ansi,x;
 cin>>n;
 for(i=1;i<=n;i++){
  scanf("%d",&a[i]);
  if(b[a[i]]&&ans>a[i]) ans=a[i],ansi=i,ansj=b[a[i]];
  b[a[i]]=i;
 }
 for(i=1;i<maxn;i++)
 for(x=0,j=i;j<maxn;j+=i){
  if(b[j]){
   if(x==0) x=j;
   else{
    if(ans>1LL*x*j/i) ans=1LL*x*j/i,ansj=b[j],ansi=b[x];
   }
  }
 }
 if(ansi>ansj) swap(ansi,ansj);
 cout<<ansi<<' '<<ansj;
   return 0;
}

Lời giải 2:

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;
const int N = 10 * 1000 * 1000 + 11;

int n;
vector<int> a;

int mind[N];

pair<int, int> mins[N];
vector<pair<int, int>> divs;

void build_sieve() {
 vector<int> pr;
 mind[0] = mind[1] = 1;
 for (int i = 2; i < N; ++i) {
  if (mind[i] == 0) {
   pr.push_back(i);
   mind[i] = i;
  }
  for (int j = 0; j < int(pr.size()) && pr[j] <= mind[i] && i * pr[j] < N; ++j) {
   mind[i * pr[j]] = pr[j];
  }
 }
}


void add_to_mins(int curd, int idx) {
    if(mins[curd].first == -1)
        mins[curd].first = idx;
    else if(mins[curd].second == -1)
        mins[curd].second = idx;
}

void rec(int pos, int curd, int idx) {
 if (pos == int(divs.size())) {
  add_to_mins(curd, idx);
  return;
 }
 int curm = 1;
 for (int i = 0; i <= divs[pos].second; ++i) {
  rec(pos + 1, curd * curm, idx);
  curm *= divs[pos].first;
 }
}

void add(int idx) {
 int value = a[idx];
 divs.clear();
 while (value > 1) {
  int d = mind[value];
  if (!divs.empty() && divs.back().first == d) {
   ++divs.back().second;
  } else {
   divs.push_back(make_pair(d, 1));
  }
  value /= d;
 }
 rec(0, 1, idx);
}

int main() {
#ifdef _DEBUG
 freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
 
 cin >> n;
 a.resize(n);
 for (int i = 0; i < n; ++i) {
  cin >> a[i];
 }
 for(int i = 0; i < N; i++)
     mins[i] = make_pair(-1, -1);
 build_sieve();
 
 vector<pair<int, int> > vals;
 for(int i = 0; i < n; i++)
     vals.push_back(make_pair(a[i], i));
 sort(vals.begin(), vals.end());
 for (int i = 0; i < n; ++i) {
     if(i > 1 && vals[i].first == vals[i - 2].first) continue;
  add(vals[i].second);
 }
 
 long long l = INF * 1ll * INF;
 int ansi = -1, ansj = -1;
 for (int i = 1; i < N; ++i) {
  pair<int, int> idxs = mins[i];
  if (idxs.second == -1) continue;
  long long curl = a[idxs.first] * 1ll * a[idxs.second] / i;
  if (l > curl) {
   l = curl;
   ansi = min(idxs.first, idxs.second);
   ansj = max(idxs.first, idxs.second);
  }
 }
 
 cout << ansi + 1 << " " << ansj + 1 << endl;
 
 return 0;
}