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

>[!Note] Thông tin
>Sau đây là lời giải của Đề 3 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_de3)
>
>:::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: Số chín ước

### Subtask 1

>[!Tip] Đếm ước
>Để đếm số lượng ước của một số $x$, ta thực hiện:
>- Duyệt từ $1$ đến $\sqrt x$, nếu $n$ chia hết cho $i$ thì nghĩa là tồn tại $2$ ước của $n$ là $i$ và $\frac{x}{i}$.
>:::warning
>Chú ý trường hợp $i = \frac{x}{i}$.
>:::

Duyệt các số từ $l$ đến $r$ và đếm số lượng số có $9$ ước.

**Độ phức tạp thời gian:** $O\left( \sqrt l + \sqrt {l+1} + \dots + \sqrt r \right)$

:::success
:::spoiler Code

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

int l, r;

int uoc(int n){
    int res = 0;
    for (int i = 1; i*i <= n; i++) {
        if (n%i == 0) {
            res += 2;
            if (i*i == n) res--;
        }
        
        if (res > 9) return res;
    }
    
    return res;
}

int main(){
    cin >> l >> r;
    
    int res = 0;
    for (int i = l; i <= r; i++)
        if (uoc(i) == 9) 
            res++;
    
    cout << res;

    return 0;
}

:::

### Subtask 2

>[!Tip] Cải tiến đếm ước
>Áp dụng kĩ thuật ==**sàng ước**==:
>- Với mỗi số $x$, lưu $cnt_x$ là số lượng ước của $x$.
>- Với mỗi số từ $1$ đến $10^6$, thực hiện duyệt qua các bội $x$ của nó và tăng $cnt_x$ lên $1$.
>
>Thao tác trên mất chi phí $O(10^6 \log 10^6)$.
>> $\frac {10^6}1 + \frac{10^6}2 + \dots + \frac{10^6}{10^6} \approx 10^6 \log 10^6$.

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

:::success
:::spoiler Code

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

const int N = 1e6 + 5;
int l, r, cnt[N];

int main(){
    //Sàng ước
    for (int i = 1; i <= 1e6; i++) {
        for (int j = i; j <= 1e6; j += i) {
            //Duyệt qua bội j của i
            cnt[j]++;
        }
    }

    cin >> l >> r;
    int res = 0;
    for (int i = l; i <= r; i++) {
        if (cnt[i] == 9) {
            res++;
        }
    }
    
    cout << res;

    return 0;
}

:::

### Subtask 3
>[!Tip] Cải tiến đếm ước
>Với một số $n = p_1^{x_1} \times p_2^{x_2} \times p_3^{x_3} \dots p_k^{x_k}$, trong đó:
> - $p_i$ là thừa số nguyên tố thứ $i$ của $n$.
> - $x_i$ là số mũ của thừa số nguyên tố thứ $i$ của $n$.
> :::success
> **Số ước của n là:**
> $$
> (x_1+1) \times (x_2+1) \times(x_3+1) \cdots(x_k+1)
> $$

Để biểu thức trên bằng $9$, ta chỉ cần xét hai trường hợp:
- $n = p^8$ (số ước của $n$ là $8 + 1 = 9$).
- $n = p_1^2 \times p_2^2$ (số ước của $n$ là $(2 + 1) \times (2 + 1) = 3 \times 3 = 9$).

Như vậy, bài toán trở thành:

==Đếm số lượng số nguyên dương $x$ có dạng $x = p^8$ và $x = p_1^2 \times p_2^2 = (p_1 \times p_2)^2$==.

Nói cách khác, đáp án chính là ==số lượng số nguyên tố mũ $8$== cộng với ==số lượng bình phương tích của hai số nguyên tố khác nhau== sao cho chúng có giá trị nằm trong đoạn $[l, r]$

>[!Tip] Đếm số lượng số nguyên tố mũ 8
>Duyệt từng số nguyên $i$ bằng vòng lặp, kiểm tra nếu $i$ là số nguyên tố và $l \le i^8 \le r$ thì $i^8$ là một số thỏa mãn đề bài.
>
>**Độ phức tạp thời gian:** $O(\sqrt[8]{r})$.
>
>:::warning
>Lưu ý, cần phải ==thoát ra== khỏi vòng lặp khi $i^8 \gt r$.
>:::

>[!Tip] Đếm số lượng bình phương của tích hai số nguyên tố khác nhau
>Ta có:
>$$
>\begin{flalign}
>(p_1 \times p_2)^2 \le r \\
>\Leftrightarrow p_1 \times p_2 \le \sqrt r
>\end{flalign}
>$$
>Đề bài cho $r \le 10^9 \Rightarrow \sqrt r \lt 31623$, như vậy ta chỉ cần xét các ==số nguyên tố nhỏ hơn hoặc bằng $31623$==.
>
>Từ $1$ đến $31623$ chỉ có $3401$ số nguyên tố. Ta lấy ra trước các số nguyên tố này, sau đó chạy hai vòng lặp lồng nhau lấy ra mọi cặp số nguyên tố.
>
>**Độ phức tạp thời gian:** $O(3401^2)$.

**Độ phức tạp thời gian của cả bài là tổng độ phức tạp thời gian của hai thao tác.**

:::success
:::spoiler Code

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

int l, r;

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

int main(){
    cin >> l >> r;

    vector<int> prime;
    //Danh sách các số nguyên tố
    
    for (int i = 2; i*i <= r; i++) {
        if (isPrime(i)) {
            prime.push_back(i);
        }
    }

    int res = 0;
    for (int i = 0; i < prime.size() - 1; i++) {
        for (int j = i+1; j < prime.size(); j++) {
            //p[i]^2 * p[j]^2
            long long x = 1ll * prime[i] * prime[i] * prime[j] * prime[j];
            if (x >= l && x <= r) res++;
        }
    }

    for (int i = 2; i*i*i*i*i*i*i*i <= r; i++) {
        //i^8
        int x = i*i*i*i*i*i*i*i;
        if (isPrime(i) && x >= l && x <= r) {
            res++;
        }
    }

    cout << res;

    return 0;
}

:::

## Bài 2: Rương tiết kiệm

### Lời giải

>[!Tip] **Nhận xét**
> Chaien luôn lấy rương có nhiều xu nhất, để đảm bảo số xu bỏ vào sẽ không phí, Suneo sẽ phải bỏ vào rương nhiều xu nhất.

Ta làm như sau:
- Sắp xếp mảng theo thứ tự giảm dần của giá trị.
- Mô phỏng Chaien đang lấy tiền, chạy vòng lặp từ $1$ đến $n$ (tức là từ rương nhiều xu nhất đến ít xu nhất), cộng số xu vào tổng nếu sau khi cộng tổng vẫn bé hơn hoặc bằng $k$. ==Tức là Chaien lấy nhiều xu nhất có thể mà không vượt quá $k$, gọi đó là $sum$.==
- Khi này, ta chỉ cần ==bỏ thêm $k - sum$ đồng xu vào rương có nhiều xu nhất== (do nhận xét ở trên).

**Độ phức tạp thời gian:** $O(n \log n)$
> $n \log n$ là số thao tác để sắp xếp mảng bằng hàm `sort()`.

:::success
:::spoiler Code

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

const int N = 3e5 + 5;
int n, a[N], k;

int main(){
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    sort (a+1, a+1+n, greater<int>());

    long long sum = 0, res = LLONG_MAX;
    for (int i = 1; i <= n; i++) {
        sum += a[i];
   
        if (sum > k) {
            break;
        }
        
        res = min(res, k - sum);
    }
    
    cout << res;

    return 0;
}

:::

## Bài 3: Bấm nút

### Lời giải

> [!Tip] **Nhận xét**:
> Dựa vào việc ==nút bấm sau phải có số điểm nhỏ hơn nút đã bấm trước đó==, ta có:
>
> Tại một vị trí $i$, sẽ không cần phải triệu hồi rô-bốt (tức là ô này đảm bảo sẽ được bấm mà tại đó không cần triệu hồi rô-bốt) khi và chỉ khi:
> - Một trong hai ô kế (ô $i-1$ và $i+1$) có số điểm lớn hơn ô $i$.
> - Một trong hai ô kế đó có số điểm bằng ô $i$ và đã được đảm bảo là sẽ được bấm.
>>Vì từ những ô kế $i$ được nhắc đến ở trên, rô-bốt có thể ==di chuyển sang== ô $i$ và bấm nút.
>

Như vây, chỉ cần phải triệu hồi ==một rô-bốt== ở vị trí bất kỳ trên một đoạn liên tiếp $[i, j]$ mà thỏa mãn:
- $a_i = a_{i+1} = \cdots = a_j$
- $a_i > a_{i-1}$ và $a_j > a_{j+1}$.
>
>**Ví dụ:** $[7, 7, 9, 9, 3, 2]$, có đoạn $[9, 9]$ thỏa mãn yêu cầu trên.
>
>Tta chỉ cần triệu hồi rô-bốt ở $1$ trong $2$ ô đó và sẽ luôn có cách di chuyển rô-bốt qua các ô xung quanh để bấm nút theo thứ tự điểm giảm dần.

Áp dụng kĩ thuật ==**hai con trỏ**==:
- Chạy vòng lặp cố định đầu $i$, đầu $j$ xuất phát từ $i$, nếu $a_{j+1} = a_j$, ta dịch đầu $j$ lên. Làm như vậy nhằm tìm được các đoạn liên tiếp bằng nhau.
- Kiểm tra điều kiện: $a_i > a_{i-1}$ và $a_j > a_{j+1}$

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

:::success
:::spoiler Code

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

const int N = 1e6 + 5;
int n, res, a[N];

int main(){
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    a[0] = a[n+1] = 0;
    
    while (i <= n) {
        int j = i;
        
        while (j < n && a[j+1] == a[i]) {
            j++;
        }
        
        if (a[i] > a[i-1] && a[j] > a[j+1]) {
            res++;
        }
        
        i = j+1;
    }
    
    cout << res;

    return 0;
}

:::

## Bài 4: Hình vuông

### Subtask 1

>[!Tip] Nhận xét
> Một hình vuông kích thước cạnh $k$ có góc trái trên là ô $[i, j]$ thì sẽ có góc phải dưới là ô $[i+k-1, j+k-1]$.
> :::success
> Để kiểm tra một hình vuông có gồm toàn số $1$ hay không, ta duyệt qua các ô trong đó để tính tổng các giá trị, tổng này phải bằng $k^2$.

Thử mọi kích thước $k$ có thể của hình vuông từ lớn đến bé, nếu có tồn tại hình vuông kích thước $k$ thì đáp án là $k$ và số lượng hình vuông có kích thước $k$.

**Độ phức tạp thời gian:** $O(n^5)$
> Đây là độ phức tạp lý thuyết - độ phức tạp thực tế sẽ nhỏ hơn nhiều, đủ để chạy với giới hạn $n, m \le 50$.

:::success
:::spoiler Code

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

const int N = 1e3 + 5;
int n, m, a[N][N];

bool full(int x, int y, int k) {
    for (int i = x; i <= x + k - 1; i++) {
        for (int j = y; j <= y + k - 1; j++) {
            if (a[i][j] == 0) {
                return 0;
            }
        }
    }
    
    return 1;
}

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

    for (int k = n; k >= 1; k--) {
        int cnt = 0, check = 0;
        for (int i = 1; i <= n - k + 1; i++) {
            for (int j = 1; j <= m - k + 1; j++) {
                 if (full(i, j, k)) {
                    check = 1;
                    cnt++;
                 }
            }
        }
        
        if (check) {
            //Ngừng chương trình để không tốn thời gian chạy
            cout << k << ' ' << cnt;
            return 0;
        }
    }

    cout << -1;

    return 0;
}

:::

### Subtask 2

>[!Tip] Nhận xét
>Có thể tạo ra hình vuông toàn $1$ cạnh $x$ có góc phải dưới là ô $[i,j]$ khi và chỉ khi $a_{i, j} = 1$ và cũng có thể tạo ra ba hình vuông toàn $1$ cạnh $x-1$ có góc phải dưới là ô $(i-1, j), (i, j-1), (i-1, j-1)$.
>

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

- **Định nghĩa:** ==$f_{i,j}$== là hình vuông lớn nhất tạo được với ô $a_{i, j}$ là góc phải dưới của hình vuông đó.
- **Công thức:** ==$f_{i, j} = \min \left(f_{i-1, j} , f_{i, j-1}, f_{i-1, j-1} \right) + 1$==
>$f_{i, j} = x$ nếu thỏa mãn đồng thời:
>- $a_{i, j} = 1$
>- $f_{i-1, j} \ge x-1$ và $f_{i, j-1} \ge x-1$ và $f_{i-1, j-1} \ge x-1$.
- **Đáp án:**
- Cạnh lớn nhất của hình vuông thỏa mãn là $\max(f_{i, j})$ với mọi $i, j$.
- Số lượng hình vuông thỏa mãn là số lượng $f_{i, j}$ bằng kết quả cạnh lớn nhất.

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

:::success
:::spoiler Code

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

const int N = 1e3 + 5;

int n, m, f[N][N], a[N][N], res = 0, mp[N];

int main() {
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == 1) {
                f[i][j] = min({f[i-1][j], f[i][j-1], f[i-1][j-1]}) + 1;
            }
            else {
                f[i][j] = 0;
            }
            
            res = max(res, f[i][j]);
            mp[f[i][j]]++;
        }
    }
    
    if (res == 0) {
        cout << -1;
    } 
    else {
        cout << res << ' ' << mp[res];
    }

    return 0;
}

:::