# Lời giải đề thi Tuyển sinh 10 tỉnh Quảng Trị - năm 2025 - môn Tin học

Tác giả: [noodles0428](https://oj.clue.edu.vn/user/noodles0428).

Chấm bài tại đây: [ClueOJ](https://oj.clue.edu.vn/contest/qt_ts10_25).

## Bài 1 - Bơm nước

### Tóm tắt đề bài

Cho 3 số nguyên dương $X, Y, K$ ($1 \le X \le Y \le 10^{12}, 1 \le K \le 10^5$). Hỏi ta cần cộng giá trị $K$ vào số $X$ bao nhiêu lần để giá trị $X$ đạt được sẽ $\ge Y$.

### Subtask 1: $X, Y \le 10^8, Y \le 10^5$

Tại subtask này, ta chỉ cần **mô phỏng** lại quá trình tăng của $X$ đến khi đạt tối thiểu là $Y$.

ĐPT: $O$($\frac{Y - X}{K}$)

### Subtask 2: Không có giới hạn gì thêm.

Gọi `diff` là hiệu giữa hai giá trị $X$ và $Y$.
- Nếu `diff` chia hết cho $K$, kết quả sẽ là $\frac{diff}{K}$.
- Trường hợp còn lại, kết quả sẽ là $\frac{diff}{K} + 1$

> Bạn đọc tự chứng minh tính chất trên.

ĐPT: $O$($1$)

## Bài 2 - Tam giác

### Tóm tắt đề bài

Cho 2 số nguyên dương $a, b$ ($1 \le a, b \le 10^9$). Đếm số lượng giá trị $c$ nguyên dương sao cho $a$, $b$, $c$ là độ dài ba cạnh của hình tam giác.

### Subtask 1: $a, b \le 10^5$

Ta có thể viết lại đề bài như sau:

Tìm giá trị $c$ thỏa mãn các điều kiện sau: $a + b > c$, $b + c > a$ và $a + c > b$.

Ta tiến hành duyệt $i$ từ $1$ đến $a + b$ và tiến hành kiểm tra xem liệu giá trị $i$ có thỏa mãn các điều kiện trên hay không.

ĐPT: $O$($a + b$)

### Subtask 2: Không có giới hạn gì thêm

Ta biến đổi bất đẳng thức như sau:
- $a + b > c$ $\rightarrow$ $c < a + b$
- $a + c > b$ $\rightarrow$ $c > b - a$
- $b + c > a$ $\rightarrow$ $c > a - b$

Do $c$ là số nguyên dương, nên tập hợp các giá trị $c \in (|a-b|, a + b)$

Suy ra, số lượng giá trị $c$ là: $(a + b - 1) - (|a - b| + 1) + 1 = a + b - |a - b| - 1$

## Bài 3 - Chia kẹo

### Tóm tắt đề bài

Cho 2 số nguyên dương $a$ và $b$ ($a, b \le 10^{12}$) lần lượt là số kẹo chanh và dừa. Hỏi có bao nhiêu cách chia sao cho số lượng kẹo mỗi loại các bạn nhận được là bằng nhau.

### Subtask 1: $A, B \le 10^7$

Ta có thể viết lại bài toán như sau: Tìm tất cả các ước số chung của $A$ và $B$.

Ta có thể duyệt $i$ từ $1$ đến $max(A, B)$ để kiểm tra xem liệu $i$ có phải là ước chung của $A$ và $B$ hay không.

ĐPT: $O$($max(A, B)$)

### Subtask 2: $A, B \le 10^{12}$

Theo phản chứng, ta có thể chứng minh như sau:

Nếu $a \times b = x$, thì ít nhất một trong hai số $a$ hoặc $b$ sẽ $\le \sqrt{x}$. Do đó, ta chỉ cần xét tới $\sqrt{max(A, B)}$ rồi làm tương tự như subtask 1.

ĐPT: $O$($\sqrt{max(A, B)}$)

### Subtask 3: Không có giới hạn gì thêm

Do giới hạn rất lớn, ta hoàn toàn không thể duyệt theo phương pháp thông thường (trial division).

Nhận xét: Với $n \le 10^{17}$, chỉ có khoảng $10^6$ ước số. Ta có thể sử dụng các thuật toán sau để có thể phân tích thừa số với giới hạn trên:
- Pollard's Rho.
- Miller-Rabin.

Từ các thừa số ta thu được, ta có thể sinh tập ước bằng đệ quy.

ĐPT: $O$($gcd(A, B)^{1/4}$)

### Bonus:
Subtask 3 là một subtask tương đối khó để cài thuật chuẩn hoàn toàn trong phòng thi, nên mình sẽ giới thiệu một cách khác có thể qua được tương đối số điểm và cài đặt cũng dễ thở hơn.

Đây là một phương pháp tối ưu từ tư tưởng **trial division**.

Ý tưởng cơ bản của thuật toán này như sau:

**Nhận xét:** Số nguyên tố $> 3$ sẽ luôn có dạng $6k + 1$ hoặc $6k - 1$ (bạn đọc tự chứng minh).

Do đó, ta có thể cài như sau:
- Xử lý riêng các thừa số nhỏ (như $2$ và $3$).
- Từ $5$ trở đi, ta có thể kiểm tra xem liệu đó có phải là thừa số nguyên tố hay không với bước nhảy $i$ là $6$.

ĐPT: $O$($\frac{\sqrt{n}}{6}$)

***Lưu ý rằng, trong một số trường hợp, phương pháp này vẫn sẽ không vượt qua tất cả các test với thời gian chạy là 1s.***

## Bài 4 - Số cameras

### Tóm tắt đề bài

Có $n$ khu vực trên một đường thẳng. Có $q$ camera tại vị trí $c_1, c_2, ..., c_q$. Mỗi camera $c_i$ giám sát từ $c_i - r$ đến $c_i + r$. Tính số lượng camera giám sát trong khu vực từ $1$ đến $n$.

Giới hạn: $1 \le n \le 10^5$, $1 \le q \le 10^5, 0 \le r < n, 1 \le c_i \le n$

### Subtask 1: $r = 0$

Mỗi camera chỉ có thể giám sát tại vị trí của chính nó. Đáp số chính là số camera từng vị trí.

ĐPT: $O$($n + q$)

### Subtask 2: $n, q \le 7000$

Với giới hạn này, ta hoàn toàn có thể **mô phỏng** lại tất cả các vị trí mà từng camera giám sát trên mảng.

ĐPT: $O$($q \times r$)

### Subtask 3 + 4: Không có giới hạn gì thêm

Đây là subtask tối ưu từ subtask 2.

Ta sẽ sử dụng [mảng hiệu (difference array)](https://wiki.vnoi.info/algo/data-structures/prefix-sum-and-difference-array.md) để có thể cập nhật hàng loạt các **đầu mút mà từng camera giám sát**. Sau đó, ta sẽ sử dụng mảng cộng dồn để có thể mô phỏng lại số lượng camera của từng vị trí $i$ với $1 \le i \le n$.

ĐPT: $O$($q + n$)