***1. Điều kiện: $\text{GCD}(A[i], A[j]) \neq 1$***
- Hai số $A[i]$ và $A[j]$ có $\text{GCD}(A[i], A[j]) \neq 1$ khi chúng có ít nhất một **thừa số nguyên tố chung**.
- Thay vì tính trực tiếp $\text{GCD}(A[i], A[j])$, ta phân tích các số trong mảng $A$ thành **các thừa số nguyên tố** và kiểm tra điều kiện dựa trên thừa số chung.
***2. Phân tích thừa số nguyên tố***
- Sử dụng thuật toán **sàng Eratosthenes** để phân tích các số từ $1$ đến $10^6$ thành các thừa số nguyên tố.
- Tạo mảng $f[x]$ lưu danh sách các thừa số nguyên tố của số $x$.
***3. Tìm vị trí gần nhất chứa các thừa số nguyên tố***
- Với mỗi số nguyên tố $p$, ta tìm về hai phía phải và trái để lưu lại vị trí gần nhất của một phần tử có số nguyên tố $p$ vào mảng $lp[p]$ (last position của $p$).
- Mục đích của $lp[p]$ là xem **số nguyên tố** $p$ xuất hiện gần nhất ở vị trí nào. Để tìm nhanh phần tử gần nhất $j$ $(j<i)$ thỏa mãn $GCD(A[i],a[j])\neq 1$
- Khi xét một phần tử $A[i]$:
- Duyệt qua tất cả các thừa số nguyên tố $p$ của $A[i]$.
- Tìm khoảng cách nhỏ nhất giữa $i$ và $lp[p]$, tức là $|(i - lp[p])|$, nếu $lp[p] \neq -1$.
- Cập nhật vị trí $lp[p] = i$ sau khi xử lý xong.
***4. Duyệt hai lượt để tối ưu kết quả***
- Duyệt từ **trái qua phải**:
- Tìm các phần tử bên phải gần nhất thỏa mãn điều kiện $\text{GCD}(A[i], A[j]) \neq 1$.
- Duyệt từ **phải qua trái**:
- Tìm các phần tử bên trái gần nhất thỏa mãn điều kiện.
- Kết hợp kết quả của cả hai lượt duyệt:
- Nếu có nhiều chỉ số thỏa mãn, chọn chỉ số $j$ nhỏ nhất.
***Độ phức tạp***
- $\text{M} = 10^6$ (giới hạn của bài)
- Phân tích thừa số nguyên tố: $O(\text{M} \cdot \log(\log(\text{M})))$.
- Tính toán khoảng cách: $O(n \cdot \log(\text{M}))$, vì mỗi số được phân tích thành tối đa $\log(\text{M})$ các thừa số nguyên tố.
- Tổng cộng: $O(n \cdot \log(\text{M}))$, phù hợp với giới hạn $n = 10^5$, $A[i] \leq 10^6$.
nhanzzzz
Created at
5 likes