Elearning CodePath – CTP Online Judge

Đường Đi Nguyên Tố

PRIMEPATH

🟢 Hard #General #Graph #Math #BFS/DFS

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho một lưới số nguyên dương $A$ kích thước $N \times M$. Mỗi ô chứa một giá trị $A[i][j]$ với $0 \le A[i][j] \le 10^{12}$.

Bạn đứng ở ô $(1, 1)$ và muốn đi đến ô $(N, M)$.
* Bạn chỉ được đi vào các ô có giá trị là số nguyên tố.
* Bạn có thể di chuyển theo 4 hướng: Trái, Phải, Lên, Xuống (sang các ô kề cạnh).

Yêu cầu: Tìm độ dài đường đi ngắn nhất từ $(1, 1)$ đến $(N, M)$.

Quy ước: Nếu ô $(1, 1)$ hoặc ô $(N, M)$ không phải là số nguyên tố, hoặc không tồn tại đường đi, hãy in ra $-1$.

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `PRIMEPATH.INP`:

* Dòng 1: Hai số nguyên $N, M$ — kích thước lưới.
* $N$ dòng tiếp theo: mỗi dòng gồm $M$ số nguyên $A[i][j]$.

Giới hạn:
* $1 \le N, M \le 2000$.
* $1 \le N \times M \le 4 \times 10^6$.
* $0 \le A[i][j] \le 10^{12}$.

---
### 📤 Định dạng Đầu ra

Ghi ra file `PRIMEPATH.OUT` một số duy nhất:
1.  Độ dài đường đi ngắn nhất, hoặc
2.  $-1$ nếu không thể đi được.

---
### ✨ Ví dụ

| Input | Output |
| :--- | :--- |
| `3 4` <br> `2 4 5 7` <br> `11 6 8 13` <br> `17 19 23 29` | `6` |

---
### 🏷 Ràng buộc – Subtask theo thuật toán kiểm tra số nguyên tố

| Tỷ lệ điểm | Ràng buộc | 
| :--- | :--- | 
| $10\%$ | $A[i][j] \le 10^6$; $N \times M \le 10^5$ | 
| $25\%$ | $A[i][j] \le 10^7$ | 
| $30\%$ | Giá trị các ô trong mỗi test nằm trong đoạn $[L, R]$, $R - L \le 10^6$ | 
| $35\%$ | $A[i][j] \le 10^{12}$ không ràng buộc theo đoạn |

---

✅ Đã AC: 2 / 9 submissions

📘 Lời giải

# 🧠 I. Hướng tiếp cận tổng quát

***

## 1) Kiểm tra số nguyên tố trên từng ô

Ta xây dựng ma trận `isPrime[i][j]`:

```latex
Giá trị isPrime[i][j] = 1 nếu A[i][j] là số nguyên tố, và = 0 ngược lại.
```

***

## 2) Tìm đường đi ngắn nhất trên lưới qua các ô nguyên tố

Ta chạy BFS:

* Mỗi ô ((i, j)) là một đỉnh.
* Hai ô kề nhau (lên, xuống, trái, phải) có cạnh nối nếu cả hai đều là số nguyên tố.

Bắt đầu từ ((1,1)), kết thúc tại ((N, M)).

Điều kiện nhanh:

* Nếu $$\\text\{isPrime\}\[1\]\[1\] = 0$$ hoặc $$\\text\{isPrime\}\[N\]\[M\] = 0$$ ⇒ kết quả là **-1**.
* BFS có độ phức tạp $(O(N \\cdot M))$, luôn đủ nhanh.

Điểm khó nằm ở việc kiểm tra số nguyên tố khi giá trị trong bảng có thể rất lớn hoặc số lượng ô nhiều.

***

# 🧩 II. Phân tích từng Subtask — Chọn thuật toán kiểm tra số nguyên tố

***

# 🔹 Subtask 1 (10%) — Trial Division

### Ràng buộc:

* $$A\[i\]\[j\] \\le 10^6$$
* $(N \\cdot M \\le 10^5)$

### Thuật toán:

Kiểm tra số nguyên tố bằng phép chia thử:

* Với $(x)$, duyệt ước từ $(2)$ đến $(\\sqrt{x})$.

Độ phức tạp cho 1 lần kiểm tra:

$O(\\sqrt{x}) \\le O(10^3)$

Tổng số phép chia:

$10^5\\times10^3=10^8$

→ Chấp nhận được trong subtask nhỏ.

### Vì sao Trial Division đủ dùng?

* $(x)$ nhỏ (tối đa $(10^6)$).
* Số lượng ô vừa phải.
* Không cần các thuật toán phức tạp hơn.

***

# 🔹 Subtask 2 (25%) — Sàng Eratosthenes

### Ràng buộc:

* $$A\[i\]\[j\] \\le 10^7$$

### Ý tưởng:

Thay vì chia thử từng số trong bảng, ta làm:

1. Tìm giá trị lớn nhất:

$V\_\{\\max\} = \\max A\[i\]\[j\]$

2. Sàng Eratosthenes từ $(2) → (V\_{max})$.
3. Kiểm tra:

$\\text\{isPrime\}\[A\[i\]\[j\]\]$

Độ phức tạp:

$O(V\_{\\max} \\log V\_{\\max}) \\approx O(10^7)$

→ Hoàn toàn đủ nhanh.

### Vì sao sàng tốt hơn Trial Division ở đây?

Nếu dùng Trial Division:

$O(N \\cdot M \\cdot \\sqrt{V\_{\\max}}) \\approx 10^6 \\cdot 3000$

→ TLE.

Sàng thì:

* Chạy một lần theo $(V\_{\\max})$
* Sau đó kiểm tra từng ô trong $(O(1))$

***

# 🔹 Subtask 3 (30%) — Segmented Sieve (Sàng trên đoạn)

### Ràng buộc:

Mọi giá trị trong bảng thuộc đoạn:

$[L, R], \\quad R - L \\le 10^6$

Nhưng:

$R \\le 10^{12}$

### Vấn đề:

* Không thể sàng từ $2$ đến $R$ vì cần mảng size $10^{12}$.
* Trial Division cho số lớn → quá chậm.

### Giải pháp:

Do đoạn ([L, R]) ngắn, dùng **Segmented Sieve**:

1. Sàng tất cả số nguyên tố $\\le \\sqrt{R}$.
2. Tạo mảng `mark[0..R-L]`, ban đầu là `true`.
3. Với mỗi số nguyên tố $p$:
    * Tìm bội đầu tiên của $p$ trong đoạn $[L, R]$
    * Gạch các bội số đó.

Một số $x = L + i$ là nguyên tố nếu:

$\\text{mark}[i] = \\text{true} \\quad \\text{và} \\quad x \\ge 2$

### Độ phức tạp:

Sàng nhỏ:

$O(\\sqrt{R} \\log R)$

Sàng trên đoạn:

$O((R - L + 1)\\log \\log R) \\approx O(10^6)$

### Tại sao Segmented Sieve tối ưu?

So sánh:

| Phương pháp | Lý do không phù hợp |
| ----------- | ------------------- |
| Sàng thường | Cần mảng đến (R) quá lớn |
| Trial Division | Kiểm tra $(10^6) số ≤ (10^{12})$ là không thể |

Segmented Sieve tận dụng **đoạn nhỏ**, nhưng hỗ trợ được số rất lớn.

***

# 🔹 Subtask 4 (35%) — Miller–Rabin (64-bit)

### Ràng buộc:

* $$A\[i\]\[j\] \\le 10^\{12\}$$
* Không đảm bảo nằm trong 1 đoạn $[L, R]$ nhỏ.

→ Segmented Sieve không còn hiệu quả.

### Giải pháp:

Sử dụng **Miller–Rabin** để kiểm tra từng số riêng lẻ.

Với các cơ số:

${2, 325, 9375, 28178, 450775, 9780504, 1795265022}$

Miller–Rabin cho kết quả **chính xác tuyệt đối** với mọi số $< 2^{64}$.

Khó nhớ quá thì dùng dãy sau cũng ok:

${2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}$

### Độ phức tạp:

$O(k \\cdot (\\log n)^3)$

với $(k)$ số cơ số cố định.

Vì:

$N \\cdot M \\le 4 \\times 10^6$

→ Tổng thời gian vẫn nhanh nếu cài đặt tốt.

### Tại sao mạnh nhất?

* Không phụ thuộc đoạn.
* Kiểm tra từng số lớn nhanh chóng.
* Không tốn bộ nhớ.

***

# 🧠 III. Tối ưu thêm (dùng cho mọi Subtask)

Dùng cache:

$\\text{primeCache}[x] = \\text{true/false}$

Nếu số xuất hiện nhiều lần trong bảng, ta không phải kiểm tra lại.

Lợi ích rõ rệt khi:

* Dữ liệu có nhiều ô trùng giá trị.
* Dùng Miller–Rabin hoặc Trial Division.

***