# Solution thi thử lần 1

## Mèo và chuột
Nếu quan sát tốt, sẽ thấy
$x$ = chiều cao mèo + (chiều cao bàn - chiều cao chuột)
$y$ = chiều cao chuột + (chiều cao bàn - chiều cao mèo)
Vậy chiều cao bàn là $(x+y)/2$

## Bãi đỗ xe khu thể chất
Bài này không đòi hỏi thuật toán gì cụ thể mà chỉ yêu cầu kĩ năng cài đặt.
Cần xử lý xâu để bóc tách ra được số $x$, trong truy vấn `IN xL` hoặc `OUT xR`. *(lưu ý $x$ có thể có nhiều chữ số) @ngọc @keobe*
Nếu khai báo các mảng $L$ và $R$ cho bên trái và bên phải thì phải if khá nhiều trường hợp, dễ sai sót $\rightarrow$ Có thể làm gọn hơn bằng cách khai báo $a[2][105]$.
Quy ước: Chữ L tương ứng với mảng $a[0]$, chữ R tương ứng với mảng $a[1]$. Sau đó chỉ cần duy nhất 1 lệnh cập nhật vào vị trí.

int a[2][105];
string s; cin >> s;
int x, side, change;
//Đọc vào truy vấn, lấy ra được các biến như trên
if ("IN") change = +1; else change = -1;
if ("L") side = 0; else side = 1;
a[side][x] += change

## Đếm nghiệm nguyên của PT
Xử lý từ "ngoài" vào "trong". Đòi hỏi nắm vững các kiến thức toán
$(a\times x+b)^c = 1$
### B1: Khi nào $a^b = 1$?
- Khi $b = 0 \Rightarrow$ luôn ra $1$ với mọi $a$
- Khi $a = 1$
- Khi $a = -1, b$ chẵn

### B2: Khi nào $a \times x + b = y$?
$\Leftrightarrow a \times x = y-b$
Keobe chú ý ở đây $y$ có thể là $1$ hoặc $-1$.
- Khi $b = y:$
- $a = 0\Rightarrow$ vô số nghiệm
- $a \neq 0 \Rightarrow$ một nghiệm $x = 0$
- $b \neq y:$ Chỉ có nghiệm nguyên khi $a \neq 0$ và $y-b$ chia hết cho $a$

Mai anh thêm code a lên đây, chừ buồn ngủ quá

## Bài code test cho Rùa
Đòi hỏi nhiều kiến thức số học.
### Bước 1: Phân tích điều kiện
Phân tích ra TSNT
Ví dụ:
$n = 2^3 . 3^5 . 5^4$
thì ước số $u$ của $n$ chỉ được phép có những thừa số $2,3,5$ khi phân tích nó ra TSNT, và số mũ phải $\le$ số mũ trong $n$
Chẳng hạn $2.3.5$ sẽ là ước của $n$ nhưng $2^4$ thì không phải.

Vậy số vừa là ước của $n!$ nhưng vừa là bội của $x$ thì phải có số mũ $\le$ trong $n!$ nhưng $\ge$ trong $x$.

### Bước 2: Code sao cho ko TLE
$n!$ là số rất lớn
Áp dụng bài toán: "Tìm bậc của SNT $p$ trong $n!$ để tính nhanh" (cái này ai chưa biết thì thả comment)
Với $x$ thì chỉ cần chạy tới căn để phân tích. Lưu ý thằng $x$ có thể có TSNT lớn tới $10^{12}$

#### 2.1. Phân tích TSNT của $n!$
Muốn phân tích TSNT của $n!$, ta phải biết số nào là số nguyên tố.
##### 2.1.1. Những số nào là số nguyên tố?
Tiến hành sàng nguyên tố từ $2 \rightarrow n$.
Cho ra mảng `isPrime[x]` cho biết $x$ có phải là số nguyên tố (`true`) hay là không (`false`)
##### 2.2.2. Phân tích
Tạo mảng `pwr[x]` cho biết số mũ của $x$ trong phân tích TSNT của $n!$. VD: $4! = 24 = 2^3*3$ thì `pwr[2] = 3, pwr[3] = 1, pwr[8] = 0, pwr[5] = 0`
Với mỗi số nguyên tố $p$, ta cần biết số mũ $k = pwr[p]$ lớn nhất sao cho $n!\ \vdots\ p^k$

1 2 3 4 5 6 7 8 9 10
  2   2   2   2   2           5 số chia hết cho 2
      2       2               2 số chia hết cho 4
              2               1 số chia hết cho 8
=================================================
               pwr[2] = k =   8

1. Đếm số lượng số chia hết cho $p$
2. Đếm số lượng số chia hết cho $p^2$
3. Đếm số lượng số chia hết cho $p^3$
4. ... cho tới khi $p^$ lớn hơn $n$ thì dừng.
5. Cuối cùng, cộng dồn lại.
#### 2.2. Phân tích TSNT của $x$
Chạy tới căn.

### Bước 1_b: Công thức
Coi như là đếm số cách điền số mũ vào mỗi vị trí, để số tạo được là ước của $n!$ và chia hết cho $x$.
Duyệt qua từng SNT $p$

$a = ..$ số mũ của $p$ trong $n!$
$b = ..$ số mũ của $p$ trong $x$
$\Rightarrow$ `đáp_án *= (a-b+1)`

TH đặc biệt: $a < b \rightarrow$ chốt đáp án $=0$