**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.

    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.

    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/