Bài G - Educatioal Round 62

Đề bài:
Bạn được cho 1 đồ thị vô hướng đặc biệt. Nó bao gồm $2n$ đỉnh được đánh số từ 1 đến 2n. Dưới đây là một số đặc tính của đồ thị:
+ Có chính xác 3n-2 cạnh trong đồ thị: n cạnh kết nối các đỉnh với số lẻ với các đỉnh có số chẵn, n-1 cạnh kết nối các đỉnh với số lẻ với nhau và n-1 cạnh kết nối các đỉnh có số chẵn với nhau.
+ Với mỗi cạnh (u,v) giữa 1 cặp các đỉnh với số lẻ, tồn tại 1 cạnh (u+1,v+1) và  ngược lại.
+ Với mỗi số lẻ u thuộc [1,2n-1], tồn tại 1 cạnh (u,u+1);
 + Đồ thi là liên thông, hơn thế nữa, nếu ta xóa tất cả các đỉnh với số lượng chẵn từ nó, và tất cả các cạnh kể với nó, đồ thị sẽ trở thành 1 cây (tương tự cho việc xóa các đỉnh lẻ).
 Vì vậy, đồ thị có thể được biểu diễn như hai cây có cùng cấu trúc, và n cạnh kết nỗi với mỗi đỉnh của cây đầu tiên tương ứng với cây thứ hai.
Các cạnh của đồ thị đều có trọng lượng. Chiều dài của một vài đường đi đơntrong đồ thị là tổng các trọng lượng của các cạnh được duyệt qua.
Đầu vào:
+ Dòng đầu tiên của đầu vào chứa 1 số nguyên n (2<=n<=3.10^5).
+ Dòng thứ 2 chứa n số nguyên $w(1,2),w(3,4),...,w(2n-1,2n)(1<=w(i,i+1)<=10^(12))$.
  Các số nguyên này mô tả trọng lượng của các cạnh kết nối với các đỉnh lẻ với đỉnh chẵn.
+n-1 dòng tiếp theo, dòng thứ i chứa 4 số nguyên x(i),y(i),w(i,1) và w(i,2).
(1<=x(i),y(i)<=n,x(i) # y(i),1<=w(i,j)<=10^(12)); nó môt tả hai cạnh;, một kết nối 2x(i)-1 với 2y(i)-1 và có trọng lượng w(i,1) ; mặt khác nối 2x(i) với 2y(i) và có trọng lương w(i,2).

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;
}