计算数组中A[i]*A[j]不是完全平方数的对数的优化算法

Question

给定一个数组，计算A[i]*A[j]不是完全平方数的(i,j)对的总数

input
n=3
input array={2,3,12}
output:2

解释2 * 3即A[0]*A[1]&2 * 12，也就是A[0]*A[2]形成完全平方。pair 2 * 3 &3 * 2为一对。my approach & code:我简单地运行2个for循环，结果是2次的时间。我怎样才能优化它。

#include <iostream>
#include<vector>
#include<cmath>
using namespace std;
bool isPerfectSquare(long long x)
{
if (x >= 0) {

long long sr = sqrt(x);
return (sr * sr == x);
}
return false;
}
int main() {
// your code goes here
long long t;cin>>t;
while(t--){
long long n;cin>>n;
vector<long long>v(n);
for(int i=0;i<n;i++){
cin>>v[i];
}
long long count=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(!isPerfectSquare(v[i]*v[j])){
count++;
}
}
}
cout<<count<<endl;
}
return 0;
}

Answer 1

技巧是首先取出所有的平方因子，您可以通过测试所有数字的可整除性来实现，直到sqrt(A[i]))。那么只有对偶才会产生完全平方积:

(2、3、12)→(2、3、3)

您可以通过计算每个值的频率来确定正方形对的数量，然后从对的总数中减去它。