Kiểm tra tích mảng số nguyên tố có phải số chính phương không (Python)

Bài toán: Cho mảng nums chứa toàn số nguyên tố, kiểm tra tích của tất cả phần tử có phải số chính phương hay không.

Quan sát

Số chính phương có mọi thừa số nguyên tố xuất hiện với số mũ chẵn. Vì mảng chỉ chứa số nguyên tố, tích sẽ là số chính phương ⟺ mỗi số nguyên tố xuất hiện số lần chẵn.

Triển khai Python

from collections import defaultdict

def solve(nums):
    freq = defaultdict(int)
    for key in nums:
        freq[key] += 1
    for key in nums:
        if freq[key] % 2 == 1:
            return False
    return True

# Test
print(solve([3, 3, 7, 7]))  # True: 3^2 * 7^2 = 441 = 21^2
print(solve([2, 3, 3]))     # False: 2^1 * 3^2 = 18 không phải chính phương

Kết quả

True

Giải thích

• Dùng defaultdict đếm tần suất mỗi số nguyên tố.
• Nếu bất kỳ tần suất nào lẻ → trả về False ngay.
• Độ phức tạp: O(n) thời gian, O(k) không gian (k = số nguyên tố khác nhau).
• Không cần tính tích thực tế (tránh tràn số).