--- author: hoangviet title: Bseq Solution --- $\Huge\text{Bseq Solution}$ ---------- :::info 🔗 Links: 📌 Tags: `random` ✍ Writer: Hoàng Việt 📄 Content: [TOC] ::: --------- ## Thuật toán **Nhận xét**: độ dài của dãy đẹp dài nhất chắc chắn sẽ $\geq \frac{n}{2}$, với $m$ = $2$. Giả sử ta có được hai vị trí bất kì trong mảng là $x$ và $y$. Ta mất độ phức tạp $O(\sqrt n)$ để tìm ra tất cả các $m$ là ước nguyên tố chung của $a_x$ và $a_y$. Số lượng $m$ đó bằng $log_2(a_i)$ Thử với mọi $m$ để tìm ra dãy đẹp dài nhất chứa cả hai vị trí $x$ và $y$ trong độ phức tạp $O(n$ * $log_2(a_i))$. ==> Độ phức tạp để tìm dãy con đẹp dài nhất chứa cả hai vị trí $x$ và $y$ là $O(\sqrt n$ + $n$ * $log_2(a_i))$ Nếu ta chọn ngẫu nhiên hai vị trí, tỷ lệ mà hai vị trí này đều nằm trong dãy con đẹp dài nhất là $\frac{1}{4}$. Và tỷ lệ sai là $\frac{3}{4}$. Nếu ta chọn ngẫu nhiên 50 lần thì tỷ lệ cả 50 lần đó đều chọn sai là $(\frac{3}{4})^{50}$, tỷ lệ này cực nhỏ $\approx 0$. Nên nếu chọn 50 lần thì kiểu gì bạn cũng có một lần chọn đúng. Với mỗi lần random ra hai vị trí $x$, $y$ thì áp dụng thuật toán trên và lấy dãy dài nhất tìm được. Độ phức tạp $O(50 * (\sqrt n$ + $n$ * $log_2(a_i)))$. ------------ Tham khảo code mẫu ở [đây](https://ideone.com/mGoLRf).