Tóm tắt đề

• Cho mảng $A$ gồm $n$ phần tử.
• Đổi chỗ ít nhất các phần tử sao cho các phần tử có giá trị là số nguyên tố tạo thành một miền liên tiếp.

Giới hạn đề bài

• Subtask 1: Có 20% test: $1\le n$, $A_{i}\le100$.
• Subtask 2: Có 30% test: $100<n$, $A_{i}\le10^{4}$.</li>
• Subtask 3: Có 50% test: $1\le n$, $A_{i}\le10^{6}$.

Lời giải

Ta nhận thấy rằng nhiệm vụ của ta đổi chỗ các giá trị là số nguyên tố sao cho chúng tạo thành 1 miền hay nói cách khác là 1 đoạn $[L, R]$. Dễ dàng nhận thấy rằng độ dài của miền này chính bằng số lượng số nguyên tố trong mảng. Từ đó bài toán trở thành tìm đoạn $[L, R]$ sao cho số lượng số không phải là số nguyên tố là ít nhất (vì khi đó ta chỉ cần đổi chỗ các số không là số nguyên tố bên trong đoạn này với số là số nguyên tố ngoài đoạn này).

Ý tưởng chính

Dùng mảng cộng dồn pre để dễ dàng tính được số lượng số không là số nguyên tố trong đoạn $[L, R]$ bất kì.

• Nếu $A{i}$ là số nguyên tố $pre{i} = pre_{i-1}+1$.
• Nếu $A{i}$ không là số nguyên tố $pre{i} = pre_{i-1}$.
• Gọi: $X$ là số lượng số nguyên tố trong mảng.
• $Y$ là số lượng số nguyên tố trong đoạn $[L, R]$ hay $Y=(pre{R}-pre{L-1})$.
• Kết quả là $min(X-Y,\forall[L,R]$ thỏa $R-L+1=X)$.

Subtask 1, 2

Tiếp cận

Duyệt từ 2 tới $\sqrt{A{i}}$ để kiểm tra $Ai$ có phải là số nguyên tố không.

Thực hiện

Duyệt từ 1 tới $n$ kiểm tra và dùng công thức nêu trên.

Độ phức tạp

$O(n\times\sqrt{n}).$

Subtask 3

Tiếp cận

Dùng sàng Eratosthenes để kiểm tra trước các số nào là số nguyên tố.

Thực hiện

Duyệt từ 1 tới $n$ kiểm tra và dùng công thức nêu trên.

Độ phức tạp

$O(n)$.