---
# System prepended metadata

title: HƯỚNG DẪN GIẢI TEST 45

---

**HƯỚNG DẪN GIẢI TEST 45 - HSG 9 VĨNH PHÚC 2022-2023**

**BÀI 1: VIẾT RỒI XOÁ**
  - Subtask 1, 2: 
    + Vét cạn với mọi $a_i$
      + Duyệt $j$ từ 1 đến $i-1$: Nếu có $a_j = a_i$ tức cả hai số này đều bị xoá, ta gán lại hai số này bằng 0.
    + Đáp án: là số lượng $a_i > 0$ còn lại
  - Subtask 3:
    + Nhận xét: Số nào xuất hiện số lần lẻ thì sẽ còn lại một số đó trên bảng. Ví dụ với $a = [2,3,2,3,2]$ thì sẽ còn lại 1 số 2 trên bảng.
    + Vậy nên ta sort dãy $a$ tăng dần rồi tách ra các đoạn bằng nhau liên tiếp, đoạn nào có số lượng là lẻ thì chứng tỏ còn một số này trên bảng --> ta tăng đáp án lên 1.
```python=
    sắp a tăng dần
    dem = 0
    j = 1
    for i từ 1 đến n:
        nếu (i=n) or (a[i] khác a[i+1]):
            m = i - j + 1
            if m là số lẻ: dem += 1
            j = i + 1
    in ra: dem
```

**BÀI 2: LẬT KÍ TỰ**
  - Vét cạn mọi vị trí $i$: ta lật để bên trái $i$ là toàn dấu '.' còn từ $i$ sang phải thì là toàn dấu '#'
  - Khi đó số thao tác lật sẽ là: (số dấu # bên trái $i$) + (số dấu . bên phải $i$).
  - Để tìm nhanh số dấu # và . thì duyệt $i$ là ta tăng số dấu # bên trái lên và giảm số dấu '.' từ $i$ sang phải đi.
```python=
    cham = số dấu . có trong xâu s
    thang = 0
    ketqua = n 
    for i từ 1 đến n:
        cham -= (s[i] = '.')
        thang += (s[i]= '#')
        ketqua = min(ketqua, thang + cham)
    in ra: ketqua
```

**BÀI 3: KHÔNG PHẢI ƯỚC SỐ**
  - Subtask 1: Tính $M$, tìm mọi ước của $M$; duyệt mọi ước $x$ của $M$ từ bé đến lớn: Nếu $x+1$ không phải là ước thì $d = x+1$ và dừng
  - Subtask 2: 
    + Với dữ liệu này ta phải nghĩ đến phân tích thừa số nguyên tố rồi
    + Để $d$ không phải ước của $M$ thì $d$ phải chứa thừa số nguyên tố nào đó có số mũ lớn hơn của $M$ có. Ví dụ $d=2^3$ thì không phải ước của $M = 2^2*3^7$.
    + Vậy nên ta phân tích mọi $a[i]$ ra thừa số nguyên tố, đánh dấu số lần xuất hiện của mỗi thừa số vào mảng đánh dấu.
    + Khi đó với i là nguyên tố thì: $d = min(d,$ luythua$(i, c[i] + 1))$
    + Để phân tích ra thừa số nguyên tố nhanh: Ta tạo mảng $e[i]$ lưu thừa số nguyên tố nhỏ nhất của $i$ rồi dùng mảng này để phân tích cho nhanh
    + Một lưu ý khi cài đặt: Cẩn thận tránh tràn số khi tính luỹ thừa.
  - Tham khảo code pascal: https://www.diffchecker.com/OR70vlBz/