Hướng dẫn cho Cặp chính phương

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\) gồm \(n\) phần tử. Hãy đếm số lượng cặp chỉ số \((i, j)\) với \(1 \leq i < j \leq n\) sao cho tích \(A_i \cdot A_j\) là một số chính phương.

Phân tích

Điều kiện: \(n \leq 10^5\), \(A_i \leq 100\).
Nhận xét quan trọng: Giá trị của các phần tử \(A_i\) rất nhỏ (tối đa là \(100\)), trong khi số lượng phần tử \(n\) khá lớn. Điều này gợi ý rằng thay vì duyệt qua các cặp phần tử trong mảng, ta nên duyệt qua các cặp giá trị có thể có từ \(1\) đến \(100\).
Một số \(x\) là số chính phương nếu tồn tại số nguyên \(k\) sao cho \(k^2 = x\).

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

Ý tưởng

Duyệt qua mọi cặp chỉ số \((i, j)\) với \(i < j\), tính tích \(A_i \cdot A_j\) và kiểm tra xem tích đó có phải là số chính phương hay không.

Độ phức tạp

Thời gian: \(O(n^2)\)
Đánh giá: Với \(n = 10^5\), \(n^2 = 10^{10}\), cách này sẽ bị quá thời gian (TLE). Cách này chỉ phù hợp với \(n \leq 5000\).

Code Brute Force

C++

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

bool is_perfect_square(long long n) {
    if (n < 0) return false;
    long long root = round(sqrt(n));
    return root * root == n;
}

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

    long long count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (is_perfect_square(1LL * a[i] * a[j])) {
                count++;
            }
        }
    }
    cout << count << endl;
    return 0;
}

Python

import math

def is_perfect_square(n):
    if n < 0: return False
    root = int(math.isqrt(n))
    return root * root == n

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

count = 0
for i in range(n):
    for j in range(i + 1, n):
        if is_perfect_square(a[i] * a[j]):
            count += 1
print(count)

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

Ý tưởng

Đếm tần suất xuất hiện của mỗi giá trị từ \(1\) đến \(100\) trong mảng \(A\). Gọi \(cnt[v]\) là số lần giá trị \(v\) xuất hiện.
Duyệt qua tất cả các cặp giá trị \((v_1, v_2)\) trong khoảng \([1, 100]\) sao cho \(v_1 \leq v_2\).
Kiểm tra xem tích \(v_1 \cdot v_2\) có phải là số chính phương hay không.
Nếu \(v_1 \cdot v_2\) là số chính phương:
- Nếu \(v_1 = v_2\): Số cặp \((A_i, A_j)\) thỏa mãn là số cách chọn 2 phần tử từ \(cnt[v_1]\) phần tử giống nhau:
  
  \[ \frac{cnt[v_1] \cdot (cnt[v_1] - 1)}{2} \]
- Nếu \(v_1 < v_2\): Số cặp \((A_i, A_j)\) thỏa mãn là tích số lần xuất hiện của hai giá trị:
  
  \[ cnt[v_1] \cdot cnt[v_2] \]
Cộng dồn các kết quả trên để có đáp án cuối cùng.

Tại sao cách này hiệu quả?

Số lượng giá trị khác nhau tối đa chỉ là \(100\). Số cặp giá trị cần kiểm tra là \(100 \cdot 101 / 2 = 5050\), một con số rất nhỏ so với \(n^2\).

Độ phức tạp

Thời gian: \(O(n + V^2)\), với \(V = \max(A_i) = 100\).
Bộ nhớ: \(O(V)\) để lưu mảng tần suất.

Code tham khảo

C++

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // Mảng đếm tần suất các giá trị từ 1 đến 100
    vector<long long> cnt(101, 0);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x <= 100) cnt[x]++;
    }

    long long ans = 0;
    // Duyệt qua mọi cặp giá trị (v1, v2)
    for (int v1 = 1; v1 <= 100; v1++) {
        if (cnt[v1] == 0) continue;
        for (int v2 = v1; v2 <= 100; v2++) {
            if (cnt[v2] == 0) continue;

            // Kiểm tra tích v1 * v2 có là số chính phương
            int product = v1 * v2;
            int root = round(sqrt(product));
            if (root * root == product) {
                if (v1 == v2) {
                    // Chọn 2 chỉ số từ các phần tử có cùng giá trị v1
                    ans += cnt[v1] * (cnt[v1] - 1) / 2;
                } else {
                    // Kết hợp các phần tử giá trị v1 với các phần tử giá trị v2
                    ans += cnt[v1] * cnt[v2];
                }
            }
        }
    }

    cout << ans << endl;
    return 0;
}

Python

import sys
import math

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:]))

    # Đếm tần suất các giá trị từ 1 đến 100
    cnt = [0] * 101
    for x in a:
        if x <= 100:
            cnt[x] += 1

    ans = 0
    # Duyệt qua các cặp giá trị (v1, v2)
    for v1 in range(1, 101):
        if cnt[v1] == 0:
            continue
        for v2 in range(v1, 101):
            if cnt[v2] == 0:
                continue

            product = v1 * v2
            root = math.isqrt(product)

            if root * root == product:
                if v1 == v2:
                    # nC2: chọn 2 trong số các phần tử giống nhau
                    ans += cnt[v1] * (cnt[v1] - 1) // 2
                else:
                    # Quy tắc nhân: chọn 1 từ v1 và 1 từ v2
                    ans += cnt[v1] * cnt[v2]

    print(ans)

if __name__ == "__main__":
    solve()

Bình luận

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

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