# Đề TS10 - BRVT - 2022: Editorial

>[!Note] Thông tin
>Sau đây là lời giải của Kỳ thi Tuyển sinh 10 trường THPT chuyên Lê Quý Đôn tỉnh Bà Rịa - Vũng Tàu năm học 2022 - 2023.
>
>**Bạn đọc có thể nộp và chấm bài (test tự sinh)** [TẠI ĐÂY](https://chuyentin-brvt.online/contest/algi_ts10_15_24).
>
>:::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

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

Cho ba số nguyên $a,b,k$.

**Yêu cầu:** Đếm số lượng số chia hết cho $k$ trong đoạn $[a, b]$.

**Dữ liệu đảm bảo:** $1 \le k, a, b \le 10^{18}$ và $a \le b$.

**Ràng buộc:**
- $40\%$ số điểm ứng với $1 \le k, a, b \le 32000$;
- $40\%$ số điểm ứng với $1 \le k, a, b \le 10^9$, $0 \le b - a \le 10^6$;
- $20\%$ số điểm ứng với $1 \le k, a, b \le 10^{18}$.

### Subtask 1 + 2

Duyệt vòng lặp $i$ từ $a$ đến $b$ rồi kiểm tra $i$ có chia hết cho $k$ không và tăng kết quả.

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

:::success
:::spoiler Code

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

long long k, a, b, res;

int main() {
    cin >> k >> a >> b;
    for (int i = a; i <= b; i++) {
        if (i % k == 0)
            res++;
    }

    cout << res;
    return 0;
}

:::

### Subtask 3

>[!Tip]
>Các số chia hết cho $k$ trong khoảng từ $1$ đến $n$ có dạng $k,2k,3k,4k, \dots ,dk$. Trong đó $d$ là số lớn nhất sao cho $d\cdot k \le n$ hay $d \le \frac nk$.
>:::success
>Mà $d$ là một số nguyên nên ==$d=\lfloor \frac nk \rfloor$==.
>:::

Như vậy, ta có thể tính nhanh số lượng số chia hết cho $k$ trong khoảng từ $1$ đến $n$ bằng cách lấy kết quả là: $\lfloor \frac n k \rfloor$.

Vậy để giải quyết bài toán trên ta sẽ lấy kết quả:
$$
\left \lfloor \frac bk \right \rfloor - \left \lfloor \frac{a-1}k \right \rfloor
$$

Là các số chia hết cho $k$ từ $1$ đến $b$ và loại đi các số chia hết cho $k$ từ $1$ đến $(a-1)$.

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

:::success
:::spoiler Code

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

long long k, a, b;

int main() {
    cin >> k >> a >> b;
    cout << b/k - (a-1)/k;
    return 0;
}

:::

## Bài 2

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

Cho hai số $a$ và $b$ ($a \lt b$), tìm số $x$ không âm nhỏ nhất để $\operatorname{UCLN}\left( a + x, \; b + x\right) = b - a$.

**Yêu cầu:** In ra số $x$ không âm nhỏ nhất tìm được

**Dữ liệu đảm bảo:** $1 \lt a \lt b \le 10^{18}$ và $x \ge 0$.

**Subtasks:**
- $50\%$ số điểm: $1 \lt a \lt b \le 10^6$.
- $50\%$ số điểm: không có ràng buộc gì thêm.

### Subtask 1

Chạy vòng lặp ==từ giá trị $0$== đến khi tìm được kết quả $x$ thỏa mãn điều kiện đề bài.

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

:::success
:::spoiler Code

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

long long a, b;

int main() {
    cin >> a >> b;
    for (int i = 0; ; i++) {
        if (__gcd(a + i, b + i) == b - a) {
            cout << i;
            break;
        }
    }
    
    return 0;
}

:::

### Subtask 2

Đối với giới hạn lớn, việc dùng vòng lặp để tìm $x$ là bất khả thi.

>[!Tip] Gọi:
>- $u = a - b$
>
>Khi đó: $a \bmod u = b \bmod u$ ($1$).

Đề ra $\operatorname{UCLN}\left( a + x, \; b + x \right) = u$, từ đó suy ra:

- $(a + x) \bmod u = 0$
- $(b + x) \bmod u = 0$

Vì tính chất ($1$), ta chỉ cần đảm bảo một trong hai điều kiện trên. Bài toán trở thành ==tìm số $x$ nhỏ nhất sao cho: $(a + x) \bmod u = 0$==.

Ta có: $(a + x) \bmod u = 0 \rightarrow x = \left(-a\right) \bmod u$.
Mà $x \ge 0 \rightarrow x = \left(- \left( a \bmod u \right ) + u\right) \bmod u = u - \left( a \bmod u \right)$

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

:::success
:::spoiler Code

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

long long a, b, u;

int main() {
    cin >> a >> b;
    u = b - a;
    cout << u - (a % u);
    return 0;
}

:::

## Bài 3

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

Cho mảng $a$ gồm $n$ phần tử và một số nguyên $k$.

**Yêu cầu:** Hãy đếm số cặp $(i,j)$ sao cho $a_i + a_j = k$ $(1 \le i \lt j \le n)$.

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

**Ràng buộc:**
- $40\%$ số điểm tương ứng với $2 \le n \le 10^3 , 1 \le a_i \le 32000$ .
- $40\%$ số điểm tương ứng với $2 \le n \le 10^5 , 1 \le a_i \le 10^6$.
- $20\%$ số điểm không có ràng buộc gì thêm.

### Subtask 1

Ta duyệt qua từng cặp $(i,j)$ trong mảng $a$, kiểm tra điều kiện rồi tăng biến đếm.

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

:::success
:::spoiler Code

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

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

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

:::

### Subtask 2

>[!Tip] Nhận xét
> Vì các phần từ trong mảng nhỏ hơn $10^6$ nên nếu $k \gt 2.10^6$ thì đáp án là 0.
> :::success
> Vậy ở subtask này ta chỉ cần giải quyết bài toán với ==$k \le 2.10^6$==
> :::

Ta cố định từng phần tử $i$, lúc này ta cần đếm số lượng phần tử $j$ $(1 \le j \lt i)$ sao cho:
$$
a_i + a_j = k \Leftrightarrow a_j = k - a_i
$$

Ta có thể xử lý việc này bằng mảng đếm.

Gọi $d_x$ là số lượng phần tử $x$ đã xuất hiện (tức là ở vị trí bé hơn $i$). Vậy với mỗi phần tử $i$ ta sẽ cộng vào kết quả là $d_{k-a_i}$.

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

:::success
:::spoiler Code

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

const int N=1e5,MAXVAL=1e6;
int n, k;
long long res;
int a[N+5], d[MAXVAL*2+5];

int main() {
    cin >> n >> k;
    if (k > 2e6){
        cout << 0;
        return 0;
    }
    
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        if (a[i] <= k) res += d[k-a[i]];
        d[a[i]]++;
    }
    
    cout << res;
    
    return 0;
}

:::

### Subtask 3

Vì sử dụng mảng đếm nên nếu phần tử $a_i$ lớn sẽ dẫn đến tràn mảng. Lúc này ta thay thể mảng đếm bằng cấu trúc dữ liệu `map`.

Độ phức tạp: $O\left(n \log n \right)$.

:::success
:::spoiler Code

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

const int N = 1e5;
int n;
long long res, k;
int a[N+5];
map<long long, int> mp;

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        res += mp[k-a[i]];
        mp[a[i]]++;
    }
    
    cout << res;
    return 0;
}

:::

## Bài 4

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

Cho mảng $a$ gồm $n$ phần tử hãy tìm dãy con dài nhất của $a$ sao cho các phần tử liền kề trong dãy con thỏa mãn các điều kiện sau:
- $0 \lt |i-j| \le 10$
- $|a_j - a_i|>0$
- $|a_j - a_i|$ là một số chính phương.

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

**Ràng buộc:**
- $20\%$ số điểm tương ứng với $1 \le n \le 20$.
- $40\%$ số điểm tương ứng với $1 \le n \le 10^3$.
- $40\%$ số điểm không có ràng buộc gì.

### Subtask 1

Ta sử dụng thuật toán quay lui sinh ra tất cả các dãy con của mảng $a$, kiểm tra điều kiện rồi lấy đáp án.

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

:::success
:::spoiler Code

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

const int N = 20;
int n, res;
int a[N+5];
vector<int> vct;

bool chinh_phuong(int x) {
    int v = sqrt(x);
    return v*v == x;
}

void back_track(int x) {
    if (x > n) {
        res = max(res, (int)vct.size());
    }
    else {
        for (int i=0; i<=1; i++){
            if (i==1) {
                if (vct.size() > 0) {
                    if (x-vct.back() > 10) continue;
                    if (abs(a[x] - a[vct.back()]) == 0) continue;
                    if (!chinh_phuong(abs(a[x] - a[vct.back()])) ) continue;
                }
                vct.push_back(x);
                back_track(x+1);
                vct.pop_back();
            }
            else back_track(x+1);
        }
    }
}

int main() {
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    back_track(1);
    cout<<res;
    return 0;
}

:::

### Subtask 2

Sử dụng thuật toán quy hoạch động.
- **Định nghĩa:** ==$f_i$== là dãy con dài nhất thỏa mã điều kiện kết thúc tại $i$.
- **Khởi gán:** ==$f_i = 1$== (dãy con luôn có ít nhất 1 phần tử là $i$).

Ta duyệt các cặp $(i,j)$.
- **Công thức:** ==$f_i= \max(f_j+1)$== nếu $(i,j)$ thỏa mãn điều kiện đề bài (thêm $a_i$ vào cuối dãy con kết thúc tại $j$ tạo ra dãy con mới kết thúc tại $i$).

Độ phức tạp: $O\left(n^2\right)$.

:::success
:::spoiler Code

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

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

bool not_stf(int x) {
    int v = sqrt(x);
    return (x == 0 || v*v != x);
}

int main() {
    cin >> n;
    for (int i=1;i<=n;i++) {
        cin >> a[i];
        f[i] = 1;
        for (int j = 1; j < i; j++){
            if (i-j>10 || not_stf(abs(a[i]-a[j]))) continue;
            f[i] = max(f[i], f[j] + 1);
        }
        res = max(res, f[i]);
    }

    cout << res;
    return 0;
}

:::

### Subtask 3

Kế thừa tư tưởng của subtask 2.

Tận dụng điều kiện $0 \lt |i-j| \le 10$, ta chỉ duyệt $j$ từ $i-10$ đến $i-1$.

Độ phức tạp: $O\left(n \times 10\right)$.
:::success
:::spoiler Code

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

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

bool not_stf(int x) {
    int v = sqrt(x);
    return x==0 || v*v!=x;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        f[i] = 1;
        for (int j = max(1, i-10); j < i; j++){
            if (not_stf(abs(a[i] - a[j]))) continue;
            f[i] = max(f[i], f[j]+1);
        }
        
        res = max(res, f[i]);
    }

    cout << res;
    return 0;
}

:::