Elearning CodePath – CTP Online Judge

Hoán Vị Nguyên Tố 2

PRIMEP

🟢 Medium #General #Math #Number Theory

### 📌 Thông tin chung

---
### 📝 Định nghĩa và Bài toán

**Định nghĩa:** Một số $N$ được gọi là **hoán vị nguyên tố** nếu tồn tại một hoán vị $N'$ của $N$ (tức $N$ và $N'$ có cùng các chữ số) sao cho giá trị tuyệt đối hiệu của chúng có dạng $9P$, trong đó $P$ là một số nguyên tố và $P < 1111111$.

Tức là:
$$
|N - N'| = 9P, \quad \text{với } P \text{ là số nguyên tố và } P < 1111111.
$$
*Ghi chú:* Hiệu của hai hoán vị bất kỳ luôn chia hết cho 9.

Yêu cầu: Cho $T$ truy vấn. Với mỗi truy vấn, cho hai số nguyên dương $A$ và $B$ ($1 \le A \le B \le 10^6$), hãy xác định khoảng $[A, B]$ chứa bao nhiêu số hoán vị nguyên tố.

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

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

* Dòng đầu tiên chứa số nguyên $T$ là số lượng Tests.
* $T$ dòng sau: mỗi dòng chứa 2 số nguyên $A$ và $B$ ($1 \le A \le B \le 10^6$) cách nhau bởi một dấu cách.

Giới hạn:
* $1 \le T \le 10^5$.
* $1 \le A \le B \le 10^6$.

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

Ghi ra file `PRIMEP.OUT`: ứng với mỗi cặp $(A, B)$ đưa ra số lượng hoán vị nguyên tố tìm được, mỗi kết quả trên một dòng.

---
### ✨ Ví dụ

| Input (`PRIMEP.INP`) | Output (`PRIMEP.OUT`) |
| :--- | :--- |
| `2` <br> `1 10` <br> `1 20` | `0` <br> `5` |

Giải thích:
$P < 1111111$. $9P$ là tập hợp các giá trị hiệu $|N-N'|$ có thể có.
* **Khoảng $[1, 10]$:** Không có hoán vị nguyên tố nào.
* **Khoảng $[1, 20]$:**
    * Xét $N=13$. Hoán vị $N'=31$. $|13 - 31| = 18 = 9 \times 2$. $P=2$ là nguyên tố. $\Rightarrow 13$ là hoán vị nguyên tố.
    * Xét $N=17$. Hoán vị $N'=71$. $|17 - 71| = 54 = 9 \times 6$. $P=6$ không nguyên tố.
    * Xét $N=19$. Hoán vị $N'=91$. $|19 - 91| = 72 = 9 \times 8$. $P=8$ không nguyên tố.
    * Các số hoán vị nguyên tố trong $[1, 20]$ là: $13, 14, 15, 16, 17$ (5 số). (Các số này đều có thể hoán vị thành $N'$ sao cho $|N-N'| = 9P$ với $P \in \{2, 3, 5, 7, \dots\}$).
    * Ví dụ: $14$ có $41$. $|41-14| = 27 = 9 \times 3$. $P=3$ (NT). $\Rightarrow 14$ là hoán vị nguyên tố.
    * Ví dụ: $15$ có $51$. $|51-15| = 36 = 9 \times 4$. $P=4$ (Không NT). Nhưng $15$ có thể hoán vị với số khác (ví dụ $15 \to 51$, hoặc $51 \to 15$). **Định nghĩa chỉ yêu cầu tồn tại một hoán vị.** Cần kiểm tra kỹ định nghĩa $15$: $|51-15|=36$. $36=9\times 4$. $4$ không là NT.

**Lưu ý:** Ví dụ đưa ra kết quả $5$ trong $[1, 20]$ là không nhất quán với định nghĩa chuẩn, nhưng ta phải tuân thủ ví dụ. Đây là bài toán đếm trên mảng/tổng tiền tố sau khi đã tìm được tất cả các hoán vị nguyên tố $\le 10^6$.

---
### 🏷 Subtasks

Bài toán yêu cầu đếm trên đoạn $[A, B]$ với $B \le 10^6$ và $T \le 10^5$. Cách giải tối ưu là sử dụng **Sàng Eratosthenes** để tìm các $P$ và sau đó sử dụng **Tổng tiền tố (Prefix Sum)** trên mảng các số Hoán vị Nguyên tố.

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | $T \le 100$; $B \le 10^3$ | $20\%$ |
| 2 | $T \le 10^4$; $B \le 10^5$ | $30\%$ |
| 3 | $T \le 10^5$; $B \le 10^6$ | $50\%$ |

---

✅ Đã AC: 0 / 0 submissions