# Ôn tập TS10 & THTB 2025 - Đề 4: Editorial

>[!Note] Thông tin
>Sau đây là lời giải của Đề 4 trong chuỗi đề ôn tập TS10 & THTB 2025.
>
>**Bạn đọc có thể nộp và chấm bài** [TẠI ĐÂY](https://chuyentin-brvt.online/contest/algi_mockts10_2025_de4)
>
>:::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)
>:::

[toc]
## Bài 1: Không tương đồng

### Nhận xét

Để không tồn tại $2$ số nguyên dương khác $1$ là ước chung của $m$ và $n$, $m$ và $n$ chỉ được phép có ước chung là ==$1$ và tối đa một số nguyên tố (có thể có hoặc không)==.

### Subtask 1

Duyệt mọi số $m \in [l,r]$, sau đó duyệt qua từng ước của $m$, và đếm số lượng ước chung của $m$ và $n$.

Nếu số lượng ước chung khác $1$ lớn hơn hoặc bằng $2$, cặp số $n, m$ này không phải là cặp số không tương đồng. Ngược lại, ta ghi nhận thêm một cặp số không tương đồng.

**Độ phức tạp thời gian:** $O((r-l+1) \times m)$.

:::success
:::spoiler Code

:::

### Subtask 2

>[!Tip] Nhận xét
>Mọi uớc chung của $n$ và $m$ đều là ước của $\text{UCLN}(n,m)$.

Như vậy, để kiểm tra hai số $n, m$ có nhiều hơn $2$ ước chung khác $1$ hay không, ta chỉ cần kiểm tra xem $\text{UCLN}(n,m)$ có không quá $2$ ước khác $1$ hay không.

Trường hợp trên chỉ xảy ra khi:
- $\text{UCLN}(n,m) = 1$
- $\text{UCLN}(n,m)$ là số nguyên tố.

Như vậy, để giải bài này, ta thực hiện kiểm tra $\text{UCLN}(n,m)$ có phải là số nguyên tố hay không với mọi $m \in [l, r]$.

:::danger
Chú ý điều kiện ==$m \not= n$==
:::

**Độ phức tạp thời gian:** $O((r-l+1) \times \log m \times \sqrt m)$.
> $\log$ là chi phí để tính $\text{UCLN}$ bằng hàm `__gcd()`.
> $\sqrt m$là chi phí để kiểm tra tính nguyên tố của $m$.

:::success
:::spoiler Code

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

bool isPrime(long long x) {
    if (x < 2) {
        return false;
    }
    
    for (long long i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            return false;
        }
    }
    
    return true;
}

int main() {
    long long n, l, r;
    cin >> n >> l >> r;

    vector<long long> ans;
    for (long long i = l; i <= r; ++i) {
        long long g = __gcd(i, n);
        if (i != n && (g == 1 || isPrime(g))) {
            ans.push_back(i);
        }
    }

    cout << ans.size() << "\n";
    for (auto x : ans) {
        cout << x << " ";
    }
    
    cout << "\n";
    
    return 0;
}

:::

## Bài 2: Xếp đĩa

### Lời giải

>[!Tip] Nhận xét
>Dễ dàng quan sất thấy, nên ==chọn đĩa có độ bền lớn nhất đặt làm đáy== vì đĩa nằm ở dưới cùng sẽ phải chịu tải nhiều nhất.
>
>Tổng quát hơn, đĩa ==càng nằm sâu ở dưới sẽ càng có độ bền lớn==, tức là độ bền của đĩa giảm dần từ dưới đáy lên đỉnh.

Như vậy, ta sắp xếp lại các chiếc đĩa theo độ bền giảm dần và lần lượt xếp những chiếc đĩa từ đầu dãy tạo thành một tháp.

Trong lúc xây tháp, ta ==kiểm tra xem có đĩa nào bị quá tải== hay không bằng cách ==duy trì biến $min$ là độ bền còn lại của đĩa có độ bền nhỏ nhất==. Một khi độ bền về $0$, ta không thể đặt thêm đĩa được nữa.

**Độ phức tạp thời gian:** $O(n \log n)$.
> Độ phức tạp của hàm `sort()`.

:::success
:::spoiler Code

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

const int N = 1e6 + 9;
int a[N];

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

    sort(a + 1, a + n + 1, greater<int>());

    int mini = a[1];
    int cnt = 1;

    for (int i = 2; i <= n; ++i) {
        if (mini <= 0) {
            break;
        }
            
        mini = min(mini - 1, a[i]);
        ++cnt;
    }

    cout << cnt;

    return 0;
}

:::

## Bài 3: Khôi phục mảng

### Lời giải

Áp dụng ==quy hoạch động==.

- Định nghĩa: ==$dp_{i, j}$== là số cách tạo ra một dãy thỏa mãn từ $1$ đến $i$, trong đó $A_i = j$.
- Khởi gán:
- Ban đầu, mọi giá trị $dp$ đều bằng $0$.
- Nếu $A_1 = 0$, ==$dp_{1,A_1} = 1$==: Chỉ có một cách đặt giá trị cho $A_1$ là $A_1$.
- Nếu $A_1 \not = 0$, ==$dp_{1,j} = 1$== với $j \in [1, m]$: Vì $A_1$ chưa xác định, có thể đặt nó bằng giá trị từ $1$ đến $m$.
- Công thức (với $i \ge 2$):
- Nếu $A_i = 0$, ==$dp_{i, j} = dp_{i-1,j-1} + dp_{i-1,j} + dp_{i-1,j+1}$==: Thử gán $A_i = j$ với $j$ chạy từ $1$ đến $m$. Nếu muốn gán $A_i = j$ thì $A_{i-1}$ không được chênh quá $1$ đơn vị với $j$, tức là chỉ có thể nhận các giá trị $j-1, j, j+1$.
- Nếu $A_i \not = 0$, ==$dp_{i, A_i} = dp_{i-1,A_i-1} + dp_{i-1,A_i} + dp_{i-1,A_i+1}$==: Chỉ có thể giữ nguyên giá trị $A_i$, khi đó $A_{i-1}$ không được chênh quá $1$ đơn vị với $A_i$, tức là chỉ có thể nhận các giá trị $A_i-1, A_i, A_i+1$.

Độ phức tạp $O(n m)$.

:::success
:::spoiler Code

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

const int N = 100006;
const int M = 105;
const int MOD = 1000000007;

int f[N][M];

int main() {
    int n, m, a;
    cin >> n >> m >> a;

    if (a == 0) {
        for (int i = 1; i <= m; ++i) {
            f[1][i] = 1;
        }
    } else {
        f[1][a] = 1;
    }

    for (int i = 2; i <= n; ++i) {
        cin >> a;
        if (a!=0) {
            f[i][a] = (f[i - 1][a + 1] + f[i - 1][a] + f[i - 1][a - 1]) % MOD;
        } else {
            for (int j = 1; j <= m; ++j) {
                f[i][j] = (f[i - 1][j + 1] + f[i - 1][j] + f[i - 1][j - 1]) % MOD;
            }
        }
    }

    int res = 0;
    for (int i = 1; i <= m; ++i) {
        res = (res + f[n][i]) % MOD;
    }

    cout << res << '\n';
    return 0;
}

:::

## Bài 4: Trung vị hình vuông

### Subtask 1

Duyệt bảng, tính giá trị ở từng ô và đưa vào một mảng. Sau đó sắp xếp lại và đưa ra số trung vị của dãy.

**Độ phức tạp thời gian:** $O(n^2 \log n^2)$.
> Ta cần sắp xếp một dãy có $n^2$ phần tử.

:::success
:::spoiler Code

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

vector<long long> V;
long long n;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			V.push_back((long long)i*j);

	sort(V.begin(), V.end());
	cout << V[n*n/2];

	return 0;
}

:::

### Subtask 2

>[!Tip] Nhận xét
> Gọi $f(x)$ là số lượng số nhỏ hơn hoặc bằng $x$ trong bảng.
>
> Đáp án của bài chính là số $x$ nhỏ nhất thỏa $f(x) \gt \lfloor \frac {n^2}2 \rfloor$. Vì $x$ tăng thì $f(x)$ cũng tăng, nên dễ dàng tính được đáp án bằng ==[**tìm kiếm nhị phân trên tập đáp án**](https://viblo.asia/p/tim-kiem-nhi-phan-tren-tap-ket-qua-ByEZkeAY5Q0)==.

Giá trị nhỏ nhất trong bảng nhân là $1$ và giá trị lớn nhất là $n^2$, đây cũng là ==khoảng đáp án== mà ta sẽ thực hiện tìm kiếm nhị phân.

Để tính $f(x)$ với một số $x$ bất kỳ, ta thực hiện như sau:
- Duyệt qua từng hàng từ $1$ đến $n$.
- Tại hàng $i$, ta có các giá trị $i, 2i, 3i, \dots, ni$ (tương ứng với ô ở cột $1, 2, \dots, n)$.
- Số lượng số nhỏ hơn hoặc bằng $x$ trong hàng $i$ là $\lfloor \frac x i \rfloor$.
> Các giá trị ở hàng $i$ có dạng $i \times j$ với $1 \le j \le n$.
> $i \times j \le x \Leftrightarrow j \le \frac x i$
> Mà $j$ là số nguyên, do đó ta lấy $\frac x i$ làm tròn xuống.

:::danger
Khi tính $f(x)$, chú ý chúng ta chỉ lấy số trong phạm vi của bảng, tức là tối đa chỉ có $n$ số. Vậy số lượng số nhỏ hơn hoặc bằng $x$ trong hàng $i$ là $\min(n, \lfloor \frac x i \rfloor)$.
:::

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

:::success
:::spoiler Code

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

long long n, res;

long long check(long long x) {
    long long cnt = 0;
    
    for (int i = 1; i <= n; i++) {
        cnt += min(x/i, n);
    }
    
    return cnt;
}

int main() {
    cin >> n;
    
    long long l = 1, r = n*n, k = (n * n ) / 2;
    while (l <= r) {
        long long mid = (l+r)/2;
        if (check(mid) > k){
            r = mid - 1;
            res = mid;
        }
        else {
            l = mid + 1;
        }
    }

    cout << res;

    return 0;
}

:::