AT_abc342_d-数论
N0_1
·
·
题解
题意
给定一个长度为 n 的序列，询问有多少组 (i, j) 满足 a_{i}\times a_{j} 为完全平方数且 i <j。
数据范围
2\leq N\leq 2\times 10^5
0\leq A_i\leq 2\times 10^5
基本结论
当正整数 x 为完全平方数时，令 x 分解质因数的结果为
x = p _ {1} ^ {k_{1}}\times p _ {2} ^ {k_{2}}\times p _ {3} ^ {k_{3}}\times p _ {i} ^ {k_{i}}
则对于所有的 k_{i}，其一定是偶数。
推论
若 x 不是完全平方数，则至少有一对 p _ {i} ^ {k_{i}} 的 k_{i} 为奇数（假设只有这一对为 2^3，例如 8），若 x\times y 为完全平方，则 y 分解质因数的结果，当且仅当存在 2^{k}，且 k 为奇数。
例如
$$y = 2^{k_{1}} \times 3 ^ {k_{2}}\times p _ {3} ^ {k_{3}}\times p _ {i} ^ {k_{i}}$$
满足 $k_{1}$ 为奇数，$k_{2}$ 为奇数，$k_{i}$为偶数（$i\ge 3$）。
### 求解
考虑到 $1$ 个 $2$ 与 $1$ 个 $3$ 的乘积为 $6$（~~思考为什么不考虑 $3$ 个 $2$ 与 $1$ 个 $3$ 的乘积？~~），对于 $a_{i} = x$，只需要考虑在 $i$ 之前，有多少个 $a_{k}$ 满足 $a_{k}$ 分解质因数后的乘积为 $6$ 即可($k < i$)，这一步可以 $O(n)$ 求解，分解质因数的时间复杂度为 $O(\sqrt n)$，总时间复杂度为 $O(n\times \sqrt n)$。
### code
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int a[N], pre[N];
int solve(int x) {
int num = 1;
for (int i = 2; i <= x / i; i++) {
int cnt = 0;
while (x % i == 0) {
cnt ++;
x /= i;
}
if (cnt & 1) num *= i;
}
return num * x;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n; cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
LL ans = 0;
for (int i = 1; i <= n; i++) {
if (!a[i]) {
ans += i - 1;
pre[0] ++;
continue ;
}
int num = solve(a[i]);
ans += pre[num] + pre[0];
pre[num] ++;
}
cout << ans << "\n";
return 0;
}
```