# 2024 THT Sơn Trà bảng B

## Bài 1:
$(n-1) \mod 6$
*MarkDown*

## Bài 2:

Thoughts:

phun 2, nghỉ 1
phun 3, nghỉ 1
phun 1, nghỉ 1
phun 2, nghỉ 1

T phút đầu phun nước, x phút sau đó nghỉ
Chu kỳ : T + x

L = bội chung NN(T1 + x, T2 + x, T3 + x, T4 + x)

BCNN = tích(a,b) / __gcd(a,b)

(S + L-1) / L * L - S

1. Tính chu kỳ chung $L = \text{lcm}({T_1 + x, T_2 + x, T_3 + x, T_4 + x})$
2. Thời điểm gần nhất sau $S$ là bắt đầu của chu kỳ? Bài toán Tiểu học https://lqdoj.edu.vn/problem/22tkha1

## Bài 3

Giá bán tối ưu là một trong các $a_i$ (among ú)


Hàm này hình như là convex?

Thuật toán:
1. Đọc vào danh sách $a$
2. Sắp xếp $a$
3. Chạy `for i` và giả sử giá bán là $a_i$. Doanh thu sẽ là $a_i \times (n-i+1)$
4. Lưu lại doanh thu max và giá tối ưu tìm được trong Bước 3

## Bài 4

### Sub 1: $n \le 5000$

Chạy ~~hai~~ vòng `for` để cố định giá trị $x$ từ đó suy ra $y$.

Chạy `for` tới bao nhiêu?

$y > x$.
$y \ge x+1$

Chạy for $x$ tới khi $(x+1)^2 - x^2 > n^2$. Vì $y > x$ nên $y^2 - x^2 \ge (x+1)^2 - x^2$. Điều kiện tương đương $2x+1 > n^2$.

### Sub 2: $n \le 10^6$

$n^2 + x^2 = y^2$

$n^2 = (y-x) \times (y+x)$

$y-x < y+x \Rightarrow y-x < \sqrt{n^2} = n$. Lý do:

Ta có $1\le a \le b \le n$. Có $n = a\times b \Rightarrow a^2 = a\times a \le a\times b=n$

==> Cách làm: Chạy for giá trị $u = y-x$, chạy từ $1$ tới $n$. Nếu $n^2$ chia hết cho $u$ thì tính được $v (= y+x) = \frac{n^2}{u}$.
Có $u,v$, tìm được $x$ (giải PT). Nếu có nghiệm thì cộng 1 vào đáp án

### Sub 3: $n \le 10^{12}$

> Có cần biết ước của $n$ không?

> **Đề bài:** Chỉ yêu cầu đếm số lượng cặp $(x,y)$, không cần chỉ ra.

Có nghiệm khi mà $(u,v)$ cùng tính chẵn lẻ
+ $u$ lẻ thì $v$ lẻ
+ $u$ chẵn thì $v$ chẵn

Điều kiện: $u\times v = n^2$

**Làm sao để đếm ước?**
:arrow_right: Dùng công thức đếm số ước và suy luận dựa trên dạng Phân tích Thừa số Nguyên tố của $n$.

Công thức đếm ước số:
- Với số $n$ được phân tích ra dạng TSNT $n=p_1^{e_1} \times p_2^{e_2} \times p_3^{e_3} \times \dots p_k^{e_k}$
- Số lượng ước là $(e_1+1) \times (e_2+1) \times (e_3+1) \times \dots (e_k+1)$ (Tích các (số mũ + 1))

~~Trường hợp:~~
~~- $n$ lẻ --> đáp án là số lượng ước của $n^2$ = hai lần số lượng ước của $n$, trừ 1~~
~~- $n$ chẵn, $n = 2^k \times X \Rightarrow n^2 = 2^{2k} \times X^2$. Đáp án = số lượng ước của $X^2$ nhân $(2k-1)$~~

#### Cách làm của Python

~~Số lượng ước ít nên có thể sinh ra toàn bộ ước của $n$ mà không cần duyệt. Với mỗi ước $d$ của $n$, lấy thêm được một ước là $\frac{n^2}{d}$ của $n^2$~~