Cho N và dãy số a1, a2, ...aN. Hãy đếm xem có bao nhiêu cặp (i, j) để tích ai*aj có đúng 4 ước dương (i

Để giải bài toán đếm số cặp (i, j) thỏa mãn điều kiện tích ai * aj có đúng 4 ước dương (với i < j), chúng ta có thể thực hiện theo các bước sau:

1. **Tính số ước dương**: Đầu tiên, ta cần xác định số ước dương của một số. Số ước dương của một số n có thể được tính thông qua các ước của n, dựa vào cách phân tích số thành tích các số nguyên tố. Nếu n = p1^e1 * p2^e2 * ... * pk^ek (với p1, p2, ..., pk là các số nguyên tố và e1, e2,..., ek là số mũ tương ứng), số uớc dương d(n) sẽ được tính theo công thức:
\[
d(n) = (e1 + 1) * (e2 + 1) * ... * (ek + 1)
\]
Do đó, có đúng 4 ước dương khi:
- n = p^3 (với p là số nguyên tố)
- n = p1 * p2 (với p1, p2 là các số nguyên tố khác nhau)

2. **Xây dựng danh sách các số có đúng 4 ước dương**: Ta cần tính tất cả các số trong khoảng từ 1 đến 10^6 và lưu lại những số có đúng 4 ước dương.

3. **Đếm cặp (i, j)**: Sử dụng một mảng để đếm số lượng các số ai có mặt trong dãy số, và sau đó cho mỗi số chính nó trong dãy, kiểm tra xem nó có nằm trong danh sách số có đúng 4 ước dương hay không. Ghi chú số lượng các số khác có mặt, và từ đó tính số cặp (i, j) thỏa mãn.

Dưới đây là một mẫu mã Python minh họa cho giải thuật trên:

```python
def count_divisors_up_to(max_n):
divisor_count = [0] * (max_n + 1)
for i in range(1, max_n + 1):
for j in range(i, max_n + 1, i):
divisor_count[j] += 1
return divisor_count

def count_pairs_with_four_divisors(numbers):
max_value = max(numbers)
divisor_count = count_divisors_up_to(max_value)

# Tìm số có đúng 4 ước dương và lưu vào tập hợp
valid_numbers = set()
for num in range(1, max_value + 1):
if divisor_count[num] == 4:
valid_numbers.add(num)

# Đếm số lượng cặp
count = 0
frequency = {}
for value in numbers:
if value in valid_numbers:
for v in valid_numbers:
if v != value: # để (ai, aj) có kiên thức khác nhau
count += frequency.get(v, 0)
# Cập nhật tần suất
frequency[value] = frequency.get(value, 0) + 1

return count

# Dữ liệu đầu vào
N = int(input().strip())
numbers = list(map(int, input().strip().split()))

result = count_pairs_with_four_divisors(numbers)
print(result)
```

Chương trình này thực hiện theo từng bước đã mô tả trên và sẽ cho ra kết quả đúng cho bài toán. Bạn có thể chạy chương trình này và nhập giá trị N và dãy số tương ứng để nhận được số lượng cặp (i, j) thỏa mãn điều kiện đã cho.