**Ta có:** Mọi số $a_i$ đều có thể phân tích được thành $a_i = x^2 \cdot y$, với $x^2$ là một số
chính phương và $y$ là thừa số nguyên tố với số mũ không lớn hơn $2$ và $y$ nhỏ nhất.
Giả sử: $a_i = x^2 \cdot y$ và $a_j = u^2 \cdot v$. Đến đây
ta có thể dễ dàng chứng minh được rằng $a_i \cdot a_j$ là số chính phương khi và chỉ khi $y = v$.
Vì vậy lúc này ta chỉ cần quan tâm đến $y$ trong việc phân tích thành $x^2 \cdot y$, và chỉ cần
đếm số cặp mà có cùng $y$. Đó cũng chính là đáp án của bài toán.
Ví dụ: $72 = 2^3 \cdot 3^2$.
- $3^2$ là thừa số có số mũ chẵn, vì vậy ta sẽ không làm gì.
- $2^3$ là thừa số có số mũ lẻ và lớn hơn $2$, vì vậy ta có thể tách nó thành $2^2 \cdot 2$.
Vậy ta có $72 = (3^2 \cdot 2^2) \cdot 2 = 6^2 \cdot 2$, trong đó $6^2$ là $x^2$ còn $2$ là $y$.
**Code tham khảo (C++):**
```cpp
ll factor(ll n) {
ll y = 1;
for (int i = 2; i * i <= n; ++i) {
int count = 0;
while (n % i == 0) {
n /= i;
count++;
}
// Xử lí với trường hợp số mũ lẻ
// nếu p^x mà x lẻ thì (x-1) chẵn
// lúc đó thừa số còn lại sau khi nhóm với
// các thừa số chẵn sẽ chỉ còn lại mũ 1
if (count % 2) y *= i;
}
if (n > 1) y *= n;
return y;
}
void solve() {
int n; cin >> n;
vector<int> a(n);
for (auto &it : a) cin >> it;
map<ll, ll> count;
ll ans = 0;
for (int i = 0; i < n; ++i) {
ll p = factor(a[i]);
ans += count[p];
count[p]++;
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
solve();
}
```
**Độ phức tạp:** $O(n \cdot sqrt(MX))$. Với $MX$ là phần tử lớn nhất trong mảng.
menkh
Created at
0 likes