# THI THỬ HSG TỈNH K9 - 2025 - II

>[!Note] Thông tin
>Sau đây là lời giải của đề thi thử Kỳ thi Chọn HSG tỉnh Bà Rịa - Vũng Tàu K9 lần II (được chuẩn bị theo **ma trận kiến thức của Sở GD&ĐT tỉnh Bà Rịa - Vũng Tàu**)
>
>**Thời gian:** 20:00 - 22:30 ngày 02/03/2025
>
>**Bạn đọc có thể nộp và chấm bài** [TẠI ĐÂY](https://chuyentinbrvt.online/contest/algi_mockhsg9lan2_2025)
>
>:::info
>Chuẩn bị bởi ==team Logica==, thuộc khuôn khổ dự án [**The Algitect (ALGI Project)**](https://www.facebook.com/algitect.project)
>:::

:::success
**Lưu ý:** Lời giải này chỉ hướng đến việc **AC (tức là đạt trọn điểm)** các bài.
:::

[toc]

## Bài 1: Nỗi sợ của loài rồng (5 điểm)

### Tóm tắt đề bài:

Có $n$ con rồng lần lượt bay đến tấn công lâu đài của Trâm.
- Những con rồng thứ ==$k, k \cdot 2, k \cdot 3, \dots$== sẽ bị kẹp đuôi.
- Những con rồng thứ ==$l, l \cdot 2, l \cdot 3, \dots$== sẽ bị cắt vuốt.

**Yêu cầu:** Đếm số lượng con rồng đã bị Trâm kẹp đuôi hoặc cắt vuốt.

**Dữ liệu bảo đảm:** $1 \le k, l \le k \cdot l, n \le 10^{18}$

**Subtasks:**
- $30\%$ số điểm: $1 \le k, l \le n \le 10^6$.
- $30\%$ số điểm: $k \cdot l \le 10^6$.
- $40\%$ số điểm: Không có ràng buộc gì thêm.

### Mô hình hóa bài toán:

Bài toán đơn giản là ==đếm số lượng số từ $1$ đến $n$ chia hết cho $k$ hoặc $l$==.

>[!Caution] Lưu ý
> Những số chia hết cho ==cả $k$ và $l$== chỉ được xem là $1$ số.

### Lời giải

>[!Tip]
>Ta có công thức sau:
>$$
>cnt_x = \left \lfloor \frac{n}{x} \right \rfloor
>$$
> Với $cnt_x$ là số lượng bội của $x$ từ $1$ đến $n$.

Như vậy, ta có thể tính được số lượng bội của $k$ và $l$ là:
$$
\left \lfloor \frac{n}{k} \right \rfloor + \left \lfloor \frac{n}{l} \right \rfloor
$$

Tuy nhiên, với phép tính trên, những số ==vừa chia hết cho $k$ vừa chia hết cho $l$== đang bị đếm lặp lại $2$ lần và cần trừ đi.

>[!Tip] Nhận xét
>Số nhỏ nhất vừa chia hết cho $k$ và vừa chia hết cho $l$ là ==bội chung nhỏ nhất== của $k$ và $l$
>:::success
>Vì vậy, ==bội== của ==bội chung nhỏ nhất== của $k$ và $l$ là những số chúng ta cần trừ đi

Ta tính được bội chung nhỏ nhất của $k$ và $l$ bằng:
$$
\frac{k \cdot l}{\operatorname{GCD}(k, l)}
$$

Kết quả bài toán là:
$$
\left \lfloor \frac{n}{k} \right \rfloor + \left \lfloor \frac{n}{l} \right \rfloor - \left \lfloor \frac{n}{\frac{k \cdot l}{\operatorname{GCD}(k, l)}} \right \rfloor
$$

**Độ phức tạp thời gian:** $O \left( \log \min(k, l) \right)$.
> Độ phức tạp trên là độ phức tạp để tính $\operatorname{GCD}$ bằng [**thuật toán Euclid**](https://wiki.vnoi.info/algo/algebra/euclid).

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

long long n, k, l;

long long __lcm(long long a, long long b) {
	return (a / __gcd(a, b)) * b;
}

int main() {
	cin >> n >> k >> l;
	cout << (n / k) + (n / l) - (n / __lcm(k, l));

	return 0;
}

:::

## Bài 2: Mật mã cổ đại (5 điểm)

### Tóm tắt đề bài:

Cho $q$ truy vấn, mỗi truy vấn gồm một số nguyên $n$.

**Yêu cầu:** In ra các ước nguyên tố của $n$ theo thứ tự giảm dần.

**Dữ liệu bảo đảm:** $1 \le q \le 10^5$ và $1 \le n \le 10^6$.

**Subtasks:**
- $20\%$ số điểm: $1 \le q, n \le 100$.
- $40\%$ số điểm: $1 \le q \le 10^4$.
- $40\%$ số điểm: Không có ràng buộc gì thêm.

### Mô hình hóa bài toán:

Thực chất, bài toán yêu cầu ==phân tích thừa số nguyên tố== của $n$.

### Lời giải:

Định nghĩa $E_i$ là ước nguyên tố ==nhỏ nhất== của $i$.
>VD: $E_2 = 2, E_9 = 3$.

Giả sử đã tính được $E_i$ với $i$ từ $1$ đến $n$, có thể tìm được tất cả các ước số nguyên tố của $n$ bằng cách không ngừng chia $n$ cho $E_n$ đến khi $n = 1$.
>VD: Phân tích thừa số nguyên tố của $n = 40$
> - $E_{40} = 2 \rightarrow n = \frac{40}{2} = 20$
> - $E_{20} = 2 \rightarrow n = \frac{20}{2} = 10$
> - $E_{10} = 2 \rightarrow n = \frac{10}{2} = 5$
> - $E_{5} = 5 \rightarrow n = \frac{5}{5} = 1$
>
> $n = 40$ có các ước nguyên tố là $2$ và $5$.

>[!Tip]
> Tạm gọi việc thực hiện tính trước mảng $E$ là ==sàng ước nguyên tố==. Đúng như tên gọi của nó, phương pháp này áp dụng tư tưởng của thuật toán ==sàng nguyên tố==.
> :::success
> Cụ thể, ta duyệt $i$ tăng dần từ $2$, nếu $i$ chưa tìm được ước nguyên tố $(E_i = 0)$, ta duyệt qua tất cả các bội của $j$ $\left( i, i \cdot 2, i \cdot 3, \dots \right)$ và đánh dấu $E_j = i$.
> :::
> Vì với mỗi số, ta duyệt qua các bội của nó, do đó thuật toán trên có độ phức tạp:
> $$
> O \left( \frac n1 + \frac n2 + \frac n2 \dots \right) \approx O \left( n \log n \right)
> $$
> Với $n$ là giá trị lớn nhất cần sàng tới.
> :::warning
> Tuy nhiên, trong thực tế, thuật toán trên chạy nhanh hơn rất nhiều vì **ta chỉ duyệt qua bội của những số nguyên tố**.
> :::

**Độ phức tạp thời gian:** $O \left( n \log n \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6;
int q, n, E[N+1];

void sieve() {
    for (int i = 2; i <= N; ++i) {
        if (!E[i]) {
            for (int j = i; j <= N; j += i) {
                E[j] = i;
            }
        }
    }
}


int main() {
    sieve();
    
    cin >> q;
    while (q--) {
        cin >> n;
        
        while (n > 1) {
            int p = E[n];
            cout << p << " ";
            while (n % p == 0) {
                n /= curr;
            }
        }
        
        cout << "\n";
    }
    
    return 0;
}

:::

## Bài 3: Chuyển nhà (5 điểm)

### Tóm tắt đề bài:

Khoa có $n$ món đồ, món đồ thứ $i$ có khối lượng là $A_i$. Cậu cần xếp các món đồ vào thùng có sức chứa tối đa là $k$.

**Yêu cầu:** Đếm số cách để Khoa chọn hai món đồ bỏ vào thùng.

**Dữ liệu bảo đảm:** $1 \le n \le 10^6$ và $1 \le A_i, k \le 10^9$.

**Subtasks:**
- $40\%$ số điểm: $2 \le n \le 10^3$.
- $60\%$ số điểm không có ràng buộc gì thêm.

### Mô hình hóa bài toán

Thực chất, bài toán yêu cầu đếm số cặp ==$i \lt j$== thỏa ==$A_i + A_j \le k$==.

### Lời giải:

Xét trường hợp ta cố định $A_i$, khi đó cần đếm số lượng $j$ thỏa:
- $j \gt i$.
- $A_j \le k - A_i$.

Điều này có thể thực hiện bằng ==tìm kiếm nhị phân== cơ bản.

>[!Caution]
> Có thể, khoảng $A_j$ thỏa mãn chứa cả $A_i$ mà ta đang cố định. Khi đó, cần trừ $A_i$ ra.

**Độ phức tạp thời gian:** $O \left( n \log n \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6;

ll n, k, ans, A[N+1];

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++){
        cin >> A[i];
    }

    sort(A+1, A+1+n);

    for(int i = 1; i < n; i++){
        if (A[i] >= k) break;
        int pos = upper_bound(A+1, A+1+n, k - a[i]) - A - 1;
        ans += max(0, pos - i);
    }

    cout << ans;

    return 0;
}

:::

## Bài 4: Hộp ma thuật (5 điểm)

### Tóm tắt đề bài:

Tí có một chiếc hộp ma thuật và được đưa cho một hằng số $K$. Có $q$ truy vấn, mỗi truy vấn thuộc một trong hai dạng:
- `+ x`: Thêm một viên ngọc có sức mạnh $x$ vào hộp.
- `- x`: Lấy ra một viên ngọc có sức mạnh $x$ (đảm bảo có ít nhất một viên trong hộp).

**Yêu cầu:** Với mỗi truy vấn, tính số cách lấy một số viên ngọc trong hộp để tổng sức mạnh bằng $K$. In ra số cách chia dư cho $998244353$

**Dữ liệu bảo đảm:** $1 \le q \le 10^5$ và $2 \le n \le 10^6$.

**Subtasks:**
- $20\%$ số điểm: $1 \le q \le 20$.
- $40\%$ số điểm: $1 \le q,k \le 200$.
- $40\%$ số điểm: Không có ràng buộc gì thêm.

### Mô hình hóa bài toán:

Với mỗi truy vấn, đếm số cách chọn một tập con trong tập hợp các số để tổng bằng $K$.

Đây là một bài toán ==quy hoạch động cái túi (balo)== điển hình.

### Lời giải:

- **Định nghĩa:** ==$dp_i$== là số cách tạo tổng bằng $i$.
- **Khởi gán:**
- ==$dp_0 = 1$==.
- ==$dp_i = 0$== với mọi $i \not = 0$.
- **Công thức:**
- Khi thêm một giá trị $x$: ==$dp_i = dp_i + dp_{i-x}$== với $i \ge x$.
> Với những cách tạo ra tổng $i - x$ ban đầu, có thể thêm giá trị $x$ để tạo tổng $i$.
- Khi xóa đi một giá trị $x$: ==$dp_i = dp_i - dp_{i-x}$==
> Với những cách tạo ra tổng $i - x$ ban đầu, nay mất đi một giá trị $x$ để tạo tổng $i$.
- **Kết quả:** ==$dp_K$==.

>[!Caution] Lưu ý:
> - Đối với truy vấn `- x` cần phải duyệt $i$ giảm dần để đảm bảo ==$dp_{i-x}$== đang lưu trạng thái của ==truy vấn trước== chứ không phải ==truy vấn hiện tại==.
> - Ngược lại, đối với truy vấn `+ x` cần phải duyệt $i$ tăng dần để ==$dp_{i-x}$== lưu trạng thái khi đã xét thêm giá trị $x$.

**Độ phức tạp thời gian:** $O \left( q \cdot K \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 5000;
const long long M = 998244353;
long long q, k, dp[N+1];

int32_t main() {
	dp[0] = 1;

	cin >> q >> k;
	while (q--) {
		char chr; int x;
		cin >> chr >> x;

		if (chr == '+')
			for (int i = k; i >= x; i--)
				(dp[i] += dp[i-x]) %= M;

		if (chr == '-')
			for (int i = x; i <= k; i++)
				(((dp[i] -= dp[i-x]) %= M) += M) %= M;

		cout << dp[k] << "\n";
	}

	return 0;
}

:::