**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.
Ý tưởng của lời giải này giống với lời giải phía dưới.
**Độ phức tạp:** $O(10^6 + N.max(logA_i))$ với $A_i$ là các phần tử trong mảng.
Ưu điểm: Nhanh hơn.
Nhược điểm: Chỉ sử dụng với $max(A_i) \leq 10^7$.
**Những điều cần biết về sàng Linear:**
- **Sàng Linear** có độ phức tạp $O(N)$ thay vì $O(N.log(logN))$ như **sàng Eratonthenes**.
- $lp[0] = lp[1] = 0$
- $lp[i] = i$ nếu $i$ là **số nguyên tố**
- $lp[i] =$ **thừa số nguyên tố nhỏ nhất của** $i$ nếu $i$ **là hợp số**
**Sàng Linear** sẽ giúp ta có được **thừa số nguyên tố nhỏ nhất** của một số, ví dụ
$20 = 2.2.5 \Rightarrow lp[20] = 2$ hoặc $11 = 11 \Rightarrow lp[11] = 11$.
Từ đó ta có thể lấy được tất cả các số nguyên tố mà tích của chúng bằng đúng số ban đầu.
Ví dụ: $A_i = 20$
- $lp[20] = 2 \Rightarrow$ Lấy được số $2$
- $20 / lp[20] = 10$
- $lp[10] = 2 \Rightarrow$ Lấy được số $2$
- $10 / lp[10] = 5$
- $lp[5] = 5 \Rightarrow$ Lấy được số $5$
- $5 / lp[5] = 1$
Ta sẽ áp dụng ý tưởng đó để tìm hết các **thừa số nguyên tố** trong $A_i$ và gán $A_i$ bằng giá trị mới
sau khi loại bỏ số mũ chẵn của các **thừa số nguyên tố** trong $A_i$.
Ví dụ $A_i = 20 \Rightarrow A_i = 5$ hay $A_i = 8 \Rightarrow A_i = 2$.
Khi đó chỉ cần duyệt lại mảng $A$ và sử dụng đếm phân phối.
**Code tham khảo (C++):**
```
void Linear(){
for(int i = 2; i <= (int) 1e6; i++){
if(lp[i] == 0){
lp[i] = i;
pr.push_back(i);
}
for(int j = 0; pr[j] * i <= (int) 1e6; j++){
lp[pr[j]*i] = pr[j];
if(pr[j] == lp[i]) break;
}
}
}
```
menkh
Created at
10 likes
justiin
Created at
0 likes