Hướng dẫn cho Số chính phương (TS10 Bắc Giang 2025)

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Tóm tắt đề bài

Cho dãy số gồm \(n\) số nguyên không âm \(a_1, a_2, \dots, a_n\). Tìm số chính phương nhỏ nhất không xuất hiện trong dãy số này. Số chính phương là các số có dạng \(k^2\) với \(k \in \{0, 1, 2, \dots\}\).

Phân tích

Điều kiện: \(n \le 10^6\), \(a_i \le 10^{12}\).
Nhận xét quan trọng:
- Có tối đa \(n\) số khác nhau trong dãy đầu vào.
- Nếu chúng ta kiểm tra các số chính phương theo thứ tự tăng dần: \(0^2, 1^2, 2^2, \dots, n^2\), ta có tổng cộng \(n+1\) số chính phương.
- Theo nguyên lý Dirichlet, trong \(n+1\) số chính phương đầu tiên, chắc chắn sẽ có ít nhất một số không xuất hiện trong dãy \(n\) phần tử đã cho.
- Do đó, số chính phương nhỏ nhất cần tìm chắc chắn không vượt quá \(n^2\). Với \(n = 10^6\), \(n^2 = 10^{12}\), phù hợp với giới hạn của \(a_i\).

Cách làm đơn giản (Brute Force)

Ý tưởng

Với mỗi số chính phương \(k^2\) (bắt đầu từ \(k=0\)), ta duyệt toàn bộ mảng \(a\) để kiểm tra xem \(k^2\) có tồn tại hay không. Nếu không tồn tại, đó chính là kết quả.

Độ phức tạp

Thời gian: \(O(n^2)\) vì có thể phải kiểm tra đến \(n\) số chính phương, mỗi lần duyệt mảng mất \(O(n)\).
Đánh giá: Chỉ phù hợp với Subtask 1 (\(n \le 10^3\)).

Code Brute Force

C++

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

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    for (long long k = 0; k <= n; k++) {
        long long target = k * k;
        bool found = false;
        for (int i = 0; i < n; i++) {
            if (a[i] == target) {
                found = true;
                break;
            }
        }
        if (!found) {
            cout << target << endl;
            return 0;
        }
    }
    return 0;
}

Python

n = int(input())
a = list(map(int, input().split()))

for k in range(n + 1):
    target = k * k
    found = False
    for x in a:
        if x == target:
            found = True
            break
    if not found:
        print(target)
        exit()

Hướng giải quyết (Tối ưu)

Thuật toán

Để tối ưu việc kiểm tra sự tồn tại của một số, ta có thể sử dụng cấu trúc dữ liệu set hoặc unordered_set (trong C++) hoặc set (trong Python). Tuy nhiên, vì chúng ta chỉ quan tâm đến các số chính phương, ta có thể thực hiện các bước sau:

Duyệt qua mảng \(a\), kiểm tra xem mỗi số \(a_i\) có phải là số chính phương hay không.
Nếu \(a_i\) là số chính phương, ta lưu nó vào một tập hợp (set) để đánh dấu đã xuất hiện.
Chạy vòng lặp \(k\) từ \(0\) đến \(n\). Số \(k^2\) đầu tiên không nằm trong tập hợp chính là đáp án.

Cách kiểm tra số chính phương

Một số \(x\) là số chính phương nếu \(\lfloor\sqrt{x}\rfloor^2 = x\). Khi sử dụng hàm sqrt, cần lưu ý sai số số thực bằng cách làm tròn hoặc kiểm tra các giá trị lân cận.

Độ phức tạp

Thời gian: \(O(n \log n)\) nếu dùng std::set hoặc \(O(n)\) nếu dùng std::unordered_set.
Bộ nhớ: \(O(n)\) để lưu trữ các số chính phương xuất hiện trong mảng.

Code tham khảo

C++

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

// Hàm kiểm tra số chính phương chính xác
bool isPerfectSquare(long long x) {
    if (x < 0) return false;
    long long r = (long long)round(sqrt((long double)x));
    return r * r == x;
}

int main() {
    // Tối ưu tốc độ nhập xuất
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    // Sử dụng unordered_set để đánh dấu các số chính phương đã xuất hiện
    unordered_set<long long> seen_squares;
    for (int i = 0; i < n; i++) {
        long long a;
        cin >> a;
        if (isPerfectSquare(a)) {
            seen_squares.insert(a);
        }
    }

    // Kiểm tra từng số chính phương từ 0^2, 1^2, ...
    for (long long k = 0; k <= n; k++) {
        long long val = k * k;
        if (seen_squares.find(val) == seen_squares.end()) {
            cout << val << endl;
            return 0;
        }
    }

    return 0;
}

Python

import math
import sys

def solve():
    # Đọc dữ liệu nhanh
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    n = int(input_data[0])
    a = list(map(int, input_data[1:]))

    seen_squares = set()

    for x in a:
        if x < 0:
            continue
        # Kiểm tra số chính phương
        root = int(math.isqrt(x))
        if root * root == x:
            seen_squares.add(x)

    # Kiểm tra k^2 từ 0 trở đi
    for k in range(n + 1):
        val = k * k
        if val not in seen_squares:
            print(val)
            return

if __name__ == "__main__":
    solve()

Bình luận

Tải bình luận...

Không có bình luận nào.