# THTB - TP Đà Nẵng 2021
## Bài 1

- 2 video đếm phân phối
- Dùng `map` C++
- Dùng `dict`, `defaultdict`, `Counter` Python

## Bài 2

Gọi $s(x)$ là hàm tính tổng các ước của số $x$

Số giàu có $F(n)$ định nghĩa là $F(n) = \argmax_i(s(i))$. Tức là $F(n) = i$ với $i$ là giá trị từ $1$ tới $n$ sao cho $s(i)$ lớn nhất có thể

### Tính tổng ước?
- Duyệt for tới căn bậc hai của $n$
- Dùng sàng nguyên tố

Mảng sàng bình thường:
- Mảng `is_prime[N]`. `is_prime[i] = true` nếu $i$ là số nguyên tố ngược lại, $i$ là hợp số.

Mảng sàng cải tiến:
- Đếm số lượng ước của mỗi số từ 1 tới $10^6$
- Tính tổng các ước của mỗi số từ 1 tới $10^6$
- *Tính toán liên quan ước chung, GCD từ 1 tới $10^6$*
- Lưu `s[i]` là tổng các ước của $i$

for (i từ 1 tới V_MAX) {
    for (tất cả bội j của i) {
        s[j] += i;
    }
} 

$O(V_{MAX} \log)$

## Bài 3

$x + y + z = N$
$0 < x \le y \le z < N$

Tam giác:
- $x + y > z$, $y + z > x$, $z + x > y$ BĐT tam giác
- Vì đã sort nên: $x + y > z$ là đủ
- Tam giác cân:
- $x = y$ hoặc
- $y = z$
- **Cạnh đáy lớn hơn cạnh bên.**
- $x = y < z$

Đặt lại biến: Gọi $u$ là cạnh bên, $v$ là cạnh đáy.

- $2u + v = N$
- $0 < u < v$
- $2u > v$

### Sub 1:
Chạy for $x,y,z$

### Sub 2:
Chạy for $u$ tính được $v$. Check điều kiện

### Sub 3:

$v = N - 2u$

Điều kiện $u < v \Leftrightarrow u < N - 2u \Leftrightarrow u < \frac{N}{3}$

Điều kiện $2u > v \Leftrightarrow 2u > N-2u \Leftrightarrow u > \frac{N}{4}$

### Sub 4:

## Bài 4

Nháp công thức

Một cách xử lý tinh tế cho trường hợp $m$ chia hết:
(caoductai orz)


## Bài 5
https://wiki.vnoi.info/vi/algo/data-structures/prefix-sum-and-difference-array