# Lời giải đề thi Tuyển sinh 10 tỉnh Thanh Hóa - năm 2025 - môn Tin học

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

## Bài 1 - Thống kê

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

Đếm số lượng số có số ước nguyên dương là chẵn trong đoạn $[A, B]$.

### Subtask 1. $B \le 10^3$

Đặt $N = B - A$.

Duyệt $i$ từ $a$ tới $b$. Sử dụng một vòng lặp nữa để đếm số ước. Nếu thỏa mãn thì tăng kết quả lên $1$.

Độ phức tạp: $O$ ($N^2$).

### Subtask 2. $B \le 10^6$

Sử dụng [sàng tổng ước](https://wiki.vnoi.info/vi/algo/math/divisors) để đếm nhanh số ước.

Độ phức tạp: $O$ ($N \times log$ $N$).

### Subtask 3. $B \le 10^{18}$

Xét số $i$, gọi $i = p_1^{q_1} \times p_2^{q_2} \times ... \times p_k^{q_k}$, số ước của $i$ là $(q_1 + 1) \times (q_2 + 1) \times ... \times (q_k + 1)$.

Để số ước của $i$ là lẻ thì mọi $q_x + 1$ đều phải lẻ, hay $q_x$ phải đều chẵn. Khi $q_x$ đều chẵn thì $i$ là số chính phương.

Vì vậy, bài toán chuyển về đếm số lượng số không là số chính phương trong $[A, B]$. Ta sẽ đếm số lượng số không là số chính phương trong $[1, B]$ (hay chính là $B - \sqrt B$), rồi trừ đi số lượng số không là số chính phương trong $[1, A - 1]$.

Độ phức tạp: $O$ ($1$).

## Bài 2 - Tháp đầy đủ

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

Cho hai số nguyên dương $A$ và $B$. Một tháp đầy đủ là một dãy các số $x_1, x_2, ..., x_k$ sao cho:
- $x_1 = A$, $x_k = B$.
- $x_i$ chia hết cho $x_{i - 1}$.
- Không tồn tại $z$ sao cho $z$ chia hết cho $x_{i - 1}$ và $x_i$ chia hết cho $z$.

Tìm độ dài của tháp đầy đủ đó, có thể chứng minh độ dài đó là duy nhất. Đồng thời trong tất cả các tháp đầy đủ, tìm tháp có $x_1 + x_2 + ... + x_k$ nhỏ nhất.

### Lời giải

- Nhận xét 1: Nếu $B$ không chia hết cho $A$, không tồn tại tháp đầy đủ. Ta in ra $-1$.
- Nhận xét 2: Đặt $z_i = \frac {x_i}{x_{i - 1}}$. Ta thấy $z_2 \times z_3 \times ... \times z_k = \frac {B}{A}$.
- Nhận xét 3: $z_i$ là số nguyên tố. Nếu $z_i$ không là số nguyên tố, ta sẽ có thể chèn thêm phần tử vào dãy đầy đủ này.

Vậy ta sẽ phân tích $\frac {B}{A}$ ra thừa số nguyên tố. Vấn đề chỉ là bố trí các thừa số này theo thứ tự nào.

Thứ tự tối ưu chắc chắn là thứ tự mà các thừa số nguyên tố tăng dần. Đây là điều dễ dàng quan sát thấy, vì ta mong muốn các số nhỏ sẽ được xuất hiện (hay có đóng góp) nhiều lần hơn các số lớn.

Độ phức tạp: $O$ ($\sqrt \frac {B}{A}$).

## Bài 3 - Tính căn

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

Tìm số $z$ lớn nhất sao cho $z$ là số lập phương và $z$ là ước của $n!$. Hãy in ra $z$ khi chia dư cho $10^9 + 7$.

Giới hạn: $n \le 10^5$.

### Subtask 1. $n \le 20$

Tính $n!$, đặt $y = \sqrt[3] z$, ta thấy $y \le 3 \times 10^6$.

Duyệt $y$, nếu $n!$ chia hết cho $y^3$ thì cập nhật vào kết quả.

Độ phức tạp: $O$ ($t \times \sqrt[3] {n!}$)

### Subtask 2. $n \le 10^5$

Nếu ta gọi $cnt_i$ là **số thừa số $i$** trong **phân tích thừa số nguyên tố** của $n!$, ta thấy, thừa số $i$ sẽ được đóng góp số lần là $\lfloor \frac {cnt_i}{3} \rfloor$ $\times 3$.

Lý do là bởi, vì ta muốn có $z$ lớn nhất, nên ta sẽ lấy số thừa số tối đa có thể, nhưng vẫn phải đảm bảo chia hết cho $3$ để thành số lập phương.

Vì vậy, ta sẽ phân tích $n!$ ra thừa số nguyên tố. Ta sẽ phân tích từng thừa số từ $1$ tới $n$ thay vì tính hẳn $n!$ rồi mới phân tích.

Về cách phân tích thừa số nguyên tố, các bạn có thể tham khảo tại [VNOI Wiki](https://wiki.vnoi.info/vi/algo/math/integer-factorization).

Độ phức tạp: $O$ ($t \times n \times \sqrt n$) hoặc $O$ ($t \times n \times log$ $n$) tùy vào phân tích thừa số nguyên tố bằng cách nào.

## Bài 4 - Tần số

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

Cho xâu $s$, tìm xâu con liên tiếp dài nhất mà có một giá trị thống trị.

Giá trị thống trị là giá trị (trong bài này là ký tự) xuất hiện nhiều hơn tổng số lần xuất hiện của các giá trị khác.

Giới hạn: $|s| \le 200000$.

### Subtask 1 + 2. $|s| \le 2000$

Với mỗi đoạn con $s[i, j]$ trong xâu $s$, ta sẽ dùng [mảng cộng dồn](https://wiki.vnoi.info/vi/algo/data-structures/prefix-sum-and-difference-array) tương ứng của $26$ ký tự để tìm xem có ký tự nào thống trị không.

Độ phức tạp: $O$ ($|s|^2 \times 26$).

### Subtask 3. $|s| \le 200000$

Ta sẽ thử duyệt cố định $26$ ký tự thống trị. Lúc này, ta gọi mảng $a_i = 1$ nếu $s_i$ là ký tự ta đang thử, và $a_i = -1$ nếu $s_i$ không là ký tự ta đang thử.

Lúc này, một đoạn con $s[l, r]$ là thỏa mãn nếu tổng của đoạn con này dương. Bài toán trở thàn tìm đoạn con dài nhất có tổng dương. Điều này có thể thực hiện bằng tổng tiền tố như trên.

Độ phức tạp: $O$ ($|s| \times 26$) hoặc $O$ ($|s| \times 26 \times log$ $|s|$), tùy cách cài đặt.