# Đề TS10 - BRVT - 2014: 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 2014 - 2015.
>
>**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: (3 điểm)

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

Cho hai số nguyên dương $n$ và $x$ $(2 \le n \le 1000,1 \le x \le 9)$. Yêu Cầu:
1. Cho biết chữ số tận cùng của $2^n$.
2. Tính giá trị của các biểu thức sau:
$$
A = \frac{1}{3}+\frac{2}{4}+\dots+\frac{n-1}{n+1}
$$

$$
B = \frac{x}{1!}+\frac{x^2}{2!}+\dots+\frac{x^n}{n!}
$$

### 1. Cho biết chữ số tận cùng của $2^n$.

**Nhận xét**:
- Nếu $n \equiv 0 \pmod{4}$ thì chữ số tận cùng của $2^n$ là 6.
- Nếu $n \equiv 1 \pmod{4}$ thì chữ số tận cùng của $2^n$ là 2.
- Nếu $n \equiv 2 \pmod{4}$ thì chữ số tận cùng của $2^n$ là 4.
- Nếu $n \equiv 3 \pmod{4}$ thì chữ số tận cùng của $2^n$ là 8.
:::info
**Chứng minh:**
- Vì $2^4 \equiv 6 \pmod{10}$ nên $2^{4k} \equiv 6 \pmod{10}$ $(k \in \mathbb{N}^*)$.
- Xét $2^n$ với $n = 4k+x$:
$$
2^n \equiv 2^{4k+x} \equiv 2^{4k} \times 2^x \equiv 6 \times 2^x \pmod{10}.
$$
- Thay lần lượt $x \in \{0 \dots 3\}$ vào biểu thức trên sẽ được điều cần chứng minh.

**Kiến thức sử dụng:**
- Chữ số tận cùng của một số nguyên dương $a$ là $a \bmod 10$.
- Nếu $a \equiv 6 \pmod{10}$ thì $a^k \equiv 6 \pmod{10}$ $(k \in \mathbb{N}^*)$.
- Mọi số nguyên dương đều có thể viết được dưới dạng $4k+x$ $(k \in \mathbb{N}, x \in \{0 \dots 3\})$.
- $a \times b \equiv (a \bmod c) \times (b \bmod c) \pmod{c}$ $(a,b \in \mathbb{N}; c \in \mathbb{N}^*)$.
:::

:::spoiler Code

int n,x;
cin >> n >> x;

switch (n % 4) {
    case 0: {
        cout << 6;
        break;
    }
    case 1: {
        cout << 2;
        break;
    }
    case 2: {
        cout << 4;
        break;
    }
    case 3: {
        cout << 8;
        break;
    }
}
cout << '\n';

:::

### 2. Tính giá trị của biểu thức $A$ và $B$.
**Tính biểu thức $A$**
- Duyệt $i$ từ $1$ đến $n-1$, mỗi lần cộng vào đáp án $\frac{i}{i+2}$.

**Tính biểu thức $B$**
- **Ý tưởng**: duyệt $i$ từ $1$ đến $n$, mỗi lần cộng vào đáp án $\frac{x^i}{i!}$
- **Vấn đề**: Việc tính riêng tử và mẫu của $\frac{x^i}{i!}$ là không khả thi do vấn đề về giới hạn lớn.
- **Giải pháp**: Gọi $a_i$ là giá trị của số thứ $i$. Dễ dàng nhận thấy $a_i = a_{i-1} \times \frac{x}{i}$ $(1 \le i \le n, a_0 = 1)$. Khi này, với mỗi $i$, tính $a_i$ từ $a_{i-1}$ rồi cộng $a_i$ vào đáp án.

:::warning
**Lưu ý**: Đáp án là số thực.
::::

:::spoiler Code

double A = 0;
for (int i = 1; i <= n-1; i++) {
    A += (double)i/(i+2);
}
double B = 0, t = 1;
for (int i = 1; i <= n; i++) {
    t *= (double) x / i;
    B += t;
}
cout << fixed << setprecision(6) << A << ' ' << B << '\n';

:::

## Bài 2: (5 điểm)
### Tóm tắt đề bài
Cho hai số nguyên dương $n$, $m$ và dãy nguyên dương $a$ gồm $n$ phần tử $(2 \le n \le 10^5,1 \le m \le 10^9)$. Yêu Cầu:
1. Liệt kê các phần tử có giá trị chẵn trong dãy $a$.
2. Cho biết dãy $a$ có tồn tại số nguyên tố nào không?
3. Cho biết có bao nhiêu cặp số $(i,j)$ thỏa mãn $a_i+a_j$ là số lẻ $(1 \le i \lt j \le n)$.
4. Cho biết giá trị của mẫu số sau khi thực hiện giản ước phân thức sau: $$\frac{a_1 \times a_2 \times \dots \times a_n}{m}$$

### 1. Liệt kê các phần tử có giá trị chẵn trong dãy $a$.
**Nhận xét**: Một số $x$ được gọi là chẵn nếu $x \equiv 0 \pmod{2}$.

:::spoiler Code

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

for (int i = 1; i <= n; i++) {
    if (a[i] % 2 == 0) {
        cout << a[i] << ' ';
    }
}
cout << '\n';

:::

### 2. Cho biết dãy $a$ có tồn tại số nguyên tố nào không?
Đơn giản duyệt qua mọi phần tử trong dãy $a$ và kiểm tra xem có số nguyên tố nào không. Tuy nhiên, vấn đề là làm sao để biết một số có phải số nguyên tố hay không?

**Thuật toán kiểm tra nguyên tố trong $O(\sqrt{n})$.**

**Nhận xét**:
- Mọi số nguyên dương $x$ đều có thể được phân tích dưới dạng $a \times b$ $(1 \le a,b \le n)$.
- Giả sử $a \le b$, khi này chứng minh được $a \le \sqrt{n}$.
:::info
**Chứng minh**:
Giả sử $a \gt \sqrt{n}$. Mà $a \le b$, suy ra $b \gt \sqrt{n}$. Khi này $a \times b \gt \sqrt{n} \times \sqrt{n} = n$ (Vô lý).
:::

Từ nhận xét trên rút ra được thuật toán:
- Nếu $\forall i \in [2, \sqrt{n}],n \not\equiv 0 \pmod{i}$ thì n là số nguyên tố. Ngược lại, n là hợp số.

:::spoiler Code

bool check_prime(int x) {
    if (x <= 1) return false;
    int t = sqrt(x);
    for (int i = 2; i <= t; i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

:::

**Thuật toán kiểm tra nguyên tố trong $O(1)$, chuẩn bị trong $O(n \log{\log{n}})$ (Sàng nguyên tố eratosthenes).**

các bạn có thể tham khảo tài liệu tại đây:
https://wiki.vnoi.info/algo/algebra/prime_sieve.md.

:::spoiler Code

bool isPrime[10005];

void sieve() {
    fill(isPrime,isPrime+10005,true);
    isPrime[0] = isPrime[1] = false;
    int t = sqrt(10000);
    for (int i = 2; i <= t; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= 10000; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

bool check_prime(int x) {
    if (x <= 1) return false;
    return isPrime[x];
}

:::

Bây giờ đã có 2 thuật toán kiểm tra số nguyên tố, bây giờ việc của ta chỉ cần duyệt qua dãy $a$ rồi thực hiện theo yêu cầu của đề bài.

:::spoiler Code

bool prime_exist = false;
for (int i = 1; i <= n; i++) {
    if (check_prime(a[i])) {
        prime_exist = true;
        break;
    }
}
cout << (prime_exist ? "YES" : "NO") << '\n';

:::

### 3. Cho biết có bao nhiêu cặp số $(i,j)$ thỏa mãn $a_i+a_j$ là số lẻ.

**Nhận xét**: $a + b$ là số lẻ $\Leftrightarrow$ $a$ và $b$ khác tính chẵn lẻ

**Ý Tưởng**:
- Duyệt qua mọi i từ $1$ đến $n$, với mỗi $a_i$, ta đếm số lượng $a_j$ $(j \lt i)$ thõa mãn $a_i + a_j \equiv 1 \pmod{2}$.
- Coi số lẻ là $1$, số chẵn là $0$. $\forall i \in \{1 \dots n\}$, nếu:
- $a_i$ = 0: Đếm số lượng số $a_j = 1$ $(j \lt i)$ xuất hiện trước đó.
- $a_i$ = 1: Đếm số lượng số $a_j = 0$ $(j \lt i)$ xuất hiện trước đó.

Việc này có thể có thể dễ dàng thực hiện bằng một mảng đếm.

:::spoiler Code

long long pair_count = 0; 
vector<int> cnt(2,0);
for (int i = 1; i <= n; i++) {
    int t = a[i] % 2;
    if (t == 0) {
        pair_count += cnt[1];   
    }
    else {
        pair_count += cnt[0];
    }
    cnt[t]++;
}   
cout << pair_count << '\n';

:::

### 4. Cho biết giá trị của mẫu số sau khi thực hiện giản ước phân thức.

Nếu ta tính riêng tử và mẫu sẽ không khả thi vì mỗi $a_i$ có thể lên tới $10^4$ và $n$ lên tới $10^5$ nên giá trị của tử tối đa có thể lên tới $(10^4)^{10^5}$, vượt quá giới hạn của kiểu long long trong **C++**. Vậy nên cần tìm một cách tiếp cận tốt hơn.

**Nhận xét**: Giá trị của mẫu nếu tối giản phân số $\frac{a}{b}$ là $\frac{b}{\gcd(a,b)}$ $(a,b \in \mathbb{N}^*)$.

Vậy việc tính mẫu số sau khi tối giản phân số $\frac{a_1 \times a_2 \times \dots \times a_n}{m}$ tương đương với việc tính $\frac{m}{\gcd(m,a_1 \times a_2 \times \dots \times a_n)}$.

:::spoiler Code

for (int i = 1; i <= n; i++) {
    m /= __gcd(m, a[i]);
}
cout << m << '\n';

:::

## Bài 3: (2 điểm)
### Tóm tắt đề bài
Dãy $a$ gồm $n$ phần tử được gọi là dãy đặc biệt nếu $\forall i \in \{1, \dots, n\}, a_i = \sum_{j=1}^i 2 \times j$.

**Ví dụ**: dãy $2,6,12,20$ là dãy đặc biệt, còn dãy $2, 5, 12, 20$ không phải dãy đặc biệt.

**Yêu cầu**: Cho dãy nguyên dương $a$ gồm $n$ phần tử. Hãy cho biết sau khi sắp xếp lại theo thứ tự tăng dần, dãy $a$ có phải dãy đặc biệt không?

### Thuật toán $O(n \log{n})$

Đơn giản chỉ cần sắp xếp lại dãy $a$ tăng dần. Nếu $\forall i \in \{1, \dots, n\}, a_i = \sum_{j=1}^i 2 \times j$ thì $a$ là dãy đặc biệt. Ngược lại, $a$ không phải dãy đặc biệt.

:::spoiler Code

cin >> n;
for (int i = 1; i <= n; i++) {
    cin >> a[i];
}
sort(a+1,a+1+n);
long long sum = 0;
for (int i = 1; i <= n; i++) {
    sum += 2 * i;
    if (a[i] != sum) {
        cout << 0;
        return 0;
    }
}
for (int i = 1; i <= n; i++) {
    cout << a[i] << '\n';
}

:::

Độ phức tạp cho việc sắp xếp là $O(n \log{n})$ và việc kiểm tra dãy $a$ có độ phức tạp $O(n)$. Vậy tựu chung thuật toán có độ phức tạp $O(n \log{n})$.

### Thuật toán $O(n)$

**Nhận xét**: Nếu $k$ là số đặc biệt thì $\exists \;i \in \mathbb{N}^*, \; k = i \times (i + 1)$.

:::info
Chứng minh:
Vì k là số đặc biệt nên k có dạng $2 + 4 + \dots + 2 \times i$ $(i \in \mathbb{N}^*)$.
Nhận thấy $2 + 4 + \dots + 2 \times i$ là tổng của một dãy số cách đều không giảm.
Áp dụng công thức tính tổng dãy số cách đều có quy luật:
$$
\text{Tổng} = \frac{(\text{Số đầu} + \text{Số cuối}) \times \text{Số số hạng}}{2}
$$

$$
\text{Số số hạng} = \frac{(\text{Số cuối} - \text{Số đầu})}{\text{Khoảng cách}} + 1
$$
Khi này:
Số số hạng của dãy là $\frac{(2 \times i - 2)}{2} + 1$.
Tổng của dãy là $\frac{(2 + 2 \times i) \times ( \frac{2 \times i - 2}{2} + 1)}{2} = i \times (i + 1)$.
:::

Để tính được $i$ nhanh, ta có thể biến đổi lại như sau:

$$
k = i \times (i + 1) \Rightarrow i^2 + i - k = 0 \; (*)
$$

Đến đây ta sử dụng công thức nghiệm cho phương trình bậc 2:

:::info
Công thức nghiệm cho phương trình bậc 2 có dạng $ax^2 + bx + c = 0 \;(a \not= 0)$:
$$
\Delta = b^2 - 4ac
$$

Trường hợp 1: Nếu $\Delta \lt 0$, phương trình vô nghiệm
Trường hợp 2: Nếu $\Delta \ge 0$, phương trình có 2 nghiệm:
$$
x = \frac{-b \pm \sqrt{\Delta}}{2a}
$$
:::

Ta có:
$$
\Delta = 1 + 4k
$$

Vì $k \in \mathbb{N}^*$ nên $\Delta > 0$, phương trình luôn có nghiệm. Nên:
$$
i = \frac{-1 \pm \sqrt{1+4k}}{2}
$$

Mà $i \ge 0$. Nên:
$$
i = \frac{-1 + \sqrt{1+4k}}{2}
$$

Vậy $\frac{-1 + \sqrt{1+4k}}{2}$ là một số nguyên dương thì k là số đặc biệt. Ngược lại, k không phải số đặc biệt.

**Ý tưởng**:
- Với mỗi $a_i$, tìm số $x$ thõa mãn $a_i = x \times (x + 1)$. Nếu $x \not\in \mathbb{N}^*$ hoặc $\exists \; j < i, \; a_j = x \times (x + 1)$, dãy $a$ không phải dãy đặc biệt. Ngược lại là đánh dấu lại $x$ bằng một mảng đánh dấu.
- Duyệt qua mảng đánh dấu từ $1$ tới $n$, nếu tồn tại số chưa được đánh dấu thì dãy $a$ không phải dãy đặc biệt. Ngược lại dãy $a$ là dãy đặc biệt.

:::spoiler Code

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

const int N = 1e6+5;

int n;
bool mark[N];

main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        long long a;
        cin >> a;
        if (a > 1LL * 1e6 * (1e6 + 1)) {
            cout << 0;
            return 0;
        }
        int t = (sqrt(4*a+1) - 1) / 2;
        if (1LL * t * (t + 1) != a || mark[t]) {
            cout << 0;
            return 0;
        }
        mark[t] = true;
    }
    for (int i = 1; i <= n; i++) {
        if (!mark[i]) {
            cout << 0;
            return 0;
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << 1LL * i * (i + 1) << '\n';
    }
}

:::