# Lời giải
Nếu bạn có thắc mắc, xin hãy liên hệ với [Fanpage AC](https://fb.com/acceptoj)
## Lớp 9
### Bài 1
#### Tag
Duyệt
#### Lời giải chi tiết
- Duyệt qua tất cả các phần tử trong chuỗi ký tự, nếu nó thuộc đoạn ['a'..'z'] thì ta tăng biến đếm thêm $1$
#### Mã nguồn mẫu
:::warning
C++ : https://ideone.com/Y5MMgI
Python: https://ideone.com/1r8hiJ
:::
#### Độ phức tạp
$O(N)$
### Bài 2
#### Tag
Sàng nguyên tố, Kiểm tra số nguyên tố, Duyệt
#### Lời giải chi tiết
- Sàng nguyên tố tạo trước một mảng snt[i]=0/1 tương ứng với việc i có phải là số nguyên tố hay không
- Duyệt giá trị từ $2$ đến $\frac{n}{2}$, nếu $i$ và $n-i$ là số nguyên tố thì ta tăng biến đếm

#### Mã nguồn mẫu
:::warning
C++ : https://ideone.com/7joqgm
Python: https://ideone.com/n9K7cZ
:::
#### Độ phức tạp
$O(N\log{(\log{N})})$
### Bài 3
#### Tag
Đếm phân phối, Duyệt
#### Lời giải chi tiết
- Số lượng bộ tộc có $n$ người chính là số lượng người thuộc bộ tộc có $n$ người chia cho số lượng người thuộc một bộ tộc.
- Ví dụ như : $4$ người đều thuộc bộ tộc có $2$ người, từ đó ta suy ra được có $2$ bộ tộc $2$ người.
- Ta tạo một mảng đánh dấu số lần xuất hiện số lượng của bộ tộc.
- Ta duyệt $x$ là tất cả các số lượng người mà một bộ tộc có thể và tính số bộ tộc có $x$ người.
#### Mã nguồn mẫu
:::warning
C++ : https://ideone.com/TQpUPO
Python: https://ideone.com/cpUtKH
:::
#### Độ phức tạp
- $O(N)$
### Bài 4
#### Tag
Tìm kiếm nhị phân, Toán, Implementation
#### Lời giải chi tiết
- Ta nhận thấy rằng bài toán đã đơn giản vì có giới hạn $n \leq 10^6$. Ta bắt đầu duyệt $i$ từ $1$, tăng dần và thêm vào một chuỗi nào đó cho đến khi độ dài chuỗi đó $\geq n$ và in ra.
#### Mã nguồn mẫu

:::warning
C++ : https://ideone.com/r8tzMT
Python: https://ideone.com/n5Bc5c
:::
#### Độ phức tạp
- $O(6N)$
## Lớp 12
### Bài 1
#### Tag
Duyệt
#### Lời giải chi tiết
- Kiểm tra ước thực sự của số này có phải là ước của số kia và ngược lại
#### Độ phức tạp
- $O(N+M)$
#### Mã nguồn mẫu
:::warning
C++ : https://ideone.com/6p0HhE
Python: https://ideone.com/CzJGJH
:::
### Bài 2
### Tag
Bit, backtrack
#### Lời giải chi tiết
- Sử dụng quay lui cơ bản với tập giá trị là ${0;1}$
#### Mã nguồn mẫu
:::warning
C++ : https://ideone.com/cIZmOh
Python: https://ideone.com/oZCPLK
:::
#### Độ phức tạp
- $O(2^N)$
### Bài 3
#### Tag
Đếm phân phối, Duyệt, Toán.
#### Lời giải chi tiết
- Tạo mảng tiền tố 2D ngang, dọc.
- Tính $D$ của tất cả các ma trận con và đánh dấu lại số lần xuất hiện $D$.
- In ra $D$ lớn nhất và số lần xuất hiện của $D$

#### Mã nguồn mẫu
:::warning
C++ : https://ideone.com/yhZsXU
Python: https://ideone.com/oZCPLK
:::
Lưu ý: Python sẽ bị TLE.
#### Độ phức tạp
- $O(N^4)$