Hướng dẫn cho Dãy đặc biệt

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ố nguyên \(a_1, a_2, \dots, a_n\). Một phần tử \(a_i\) được gọi là đặc biệt nếu tồn tại một chỉ số \(j \ne i\) sao cho \(a_i + a_j\) là một số chính phương. Hãy đếm số lượng phần tử đặc biệt trong dãy.

Phân tích

  • Điều kiện: \(n \le 2 \cdot 10^5\), \(0 \le a_i \le 10^6\).
  • Nhận xét 1: Tổng của hai số bất kỳ trong dãy \(a_i + a_j\) sẽ nằm trong khoảng từ \(0\) đến \(2 \cdot 10^6\).
  • Nhận xét 2: Các số chính phương trong khoảng \([0, 2 \cdot 10^6]\) không quá nhiều. Số chính phương lớn nhất cần xét là \(1414^2 = 1,999,396\). Có khoảng 1415 số chính phương như vậy.
  • Nhận xét 3: Một phần tử \(a_i\) là đặc biệt nếu tồn tại một số chính phương \(S\) sao cho giá trị \(need = S - a_i\) xuất hiện trong dãy tại một vị trí khác \(i\).

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

Ý tưởng

Với mỗi phần tử \(a_i\), ta duyệt qua tất cả các phần tử \(a_j\) còn lại (\(j \ne i\)). Kiểm tra xem \(a_i + a_j\) có phải là số chính phương hay không bằng cách dùng hàm sqrt().

Độ phức tạp

  • Thời gian: \(O(n^2)\)
  • Đánh giá: Với \(n = 2 \cdot 10^5\), \(n^2 = 4 \cdot 10^{10}\), cách này sẽ bị quá thời gian (TLE). Cách này chỉ phù hợp cho Subtask 1 (\(n \le 4000\)).

Code Brute Force

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

bool is_square(long long x) {
    if (x < 0) return false;
    long long s = sqrt(x);
    return s * s == x;
}

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

    int res = 0;
    for (int i = 0; i < n; i++) {
        bool ok = false;
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            if (is_square(a[i] + a[j])) {
                ok = true;
                break;
            }
        }
        if (ok) res++;
    }
    cout << res;
    return 0;
}
Python
Python
import math

def is_square(x):
    if x < 0: return False
    s = int(math.isqrt(x))
    return s * s == x

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

res = 0
for i in range(n):
    ok = False
    for j in range(n):
        if i == j: continue
        if is_square(a[i] + a[j]):
            ok = True
            break
    if ok:
        res += 1
print(res)

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

Ý tưởng

Thay vì duyệt qua từng cặp \((i, j)\), ta sẽ đếm số lần xuất hiện của mỗi giá trị trong dãy bằng một mảng tần suất cnt. Sau đó, với mỗi phần tử \(a_i\), ta duyệt qua danh sách các số chính phương \(S\) có thể có.

Các bước thực hiện

  1. Đếm số lần xuất hiện của mỗi giá trị \(a_i\) và lưu vào mảng cnt (kích thước \(10^6 + 1\)).
  2. Tạo danh sách các số chính phương squares từ \(0\) đến \(2 \cdot 10^6\).
  3. Với mỗi phần tử \(a_i\) trong dãy:
    • Duyệt qua từng số chính phương \(S\) trong danh sách.
    • Tính giá trị cần tìm: \(need = S - a_i\).
    • Kiểm tra điều kiện:
      • Nếu \(need < 0\) hoặc \(need > 10^6\), bỏ qua.
      • Nếu \(need \ne a_i\) và cnt[need] > 0: \(a_i\) là số đặc biệt.
      • Nếu \(need = a_i\) và cnt[a_i] > 1: \(a_i\) là số đặc biệt (vì tồn tại một vị trí \(j \ne i\) khác có cùng giá trị).
    • Nếu tìm thấy \(need\) thỏa mãn, tăng biến đếm kết quả và dừng việc kiểm tra số chính phương cho \(a_i\) hiện tại.

Độ phức tạp

  • Thời gian: \(O(n + \max(a_i) + n \times \sqrt{2 \cdot \max(a_i)})\). Với \(\max(a_i) = 10^6\), số lượng số chính phương khoảng \(1415\), tổng số phép tính khoảng \(2 \cdot 10^5 \times 1415 \approx 2.8 \cdot 10^8\). Tuy nhiên, thực tế sẽ nhanh hơn do nhiều giá trị \(need\) nằm ngoài phạm vi.
  • Bộ nhớ: \(O(\max(a_i))\) để lưu mảng tần suất.

Code tham khảo

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

const int MAXA = 1000000;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);
    vector<int> cnt(MAXA + 1, 0);

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

    // Tạo danh sách các số chính phương có thể đạt được (tổng tối đa 2,000,000)
    vector<int> squares;
    for (int i = 0; i * i <= 2 * MAXA; i++) {
        squares.push_back(i * i);
    }

    int res = 0;
    for (int i = 0; i < n; i++) {
        int x = a[i];
        bool ok = false;

        for (int s : squares) {
            int need = s - x;

            // Nếu giá trị cần tìm âm, số chính phương s quá nhỏ, thử s tiếp theo
            if (need < 0) continue;
            // Nếu giá trị cần tìm vượt quá max a_i, các s sau cũng sẽ vượt quá
            if (need > MAXA) break;

            if (cnt[need] > 0) {
                // Nếu need khác x, chắc chắn tồn tại j sao cho a[j] = need
                // Nếu need bằng x, cần ít nhất 2 số có giá trị x trong dãy
                if (need != x || cnt[x] > 1) {
                    ok = true;
                    break;
                }
            }
        }
        if (ok) res++;
    }

    cout << res;
    return 0;
}
Python
Python
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:]))

    max_val = 1000000
    cnt = [0] * (max_val + 1)
    for x in a:
        cnt[x] += 1

    # Tạo danh sách các số chính phương
    squares = []
    i = 0
    while i * i <= 2 * max_val:
        squares.append(i * i)
        i += 1

    res = 0
    for x in a:
        is_special = False
        for s in squares:
            need = s - x
            if need < 0:
                continue
            if need > max_val:
                break

            if cnt[need] > 0:
                if need != x or cnt[x] > 1:
                    is_special = True
                    break

        if is_special:
            res += 1

    print(res)

if __name__ == "__main__":
    solve()

Bình luận

Mới nhất
Tải bình luận...

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