检查数组中完美对的数量

Question

给定一个包含 N 个整数的 A 数组。如果一对索引 (i,j) (i < j) 的元素的乘积是完全平方，则这些索引对称为“完美对”。完全平方是一个正整数，它是一个整数与其自身的乘积。求 A 中完美对的数量。

我尝试解决这个问题。最初我在地图上记录了数字。我的方法是，如果数组中有 1 和一个完全平方数，我就会计算它们。然后我会检查数组中的数字，如 (3,3,3)，这将产生 3 对，这是我从(数字计数(数字计数 - 1))/2 * 公式中得到的。但这种方法对于某些测试用例给出了错误的 ans，我不知道为什么。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> v(n,0);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    int cnt=0;
    int cnt1=0;
    unordered_map<int,int> count;
    for(int i=0;i<n;i++){
        count[v[i]]++;
                // count for 1's
        if(v[i]==1){
            cnt1++;
        }
    }
    for(auto it: count){
        //check how many perfect squares can be formed--> eg(3,3,3,3,3)
        if(it.second!=0){
            int n=it.second;
            cnt+=(n*(n-1))/2;
        }
        //check for pair of 1 and perfect square--> eg(1,16)
        if(it.first!=1){
            int num=sqrt(it.first);
            if(num*num==it.first){
                cnt=cnt+(cnt1*it.second);
            }
        }
    }
    cout<<cnt<<endl;
    return 0;
}

Answer 1

首先让我们考虑一下。

\n

然后请注意，任何出现偶数次的质因数并不重要，因此我们可以丢弃每个质数出现偶数次的情况。本质上，我们将每个数字除以我们能得到的最大完全平方数。例如，我们使用2\xc3\x973=6而不是数字48600 = 2 ³ \xc3\x973 ⁵ \xc3\x975 ²，因为我们可以丢弃（= 将原始数字除以） 2 ² \xc3\x973 ⁴ \xc3\x975 ²。

\n

变换后，每个质因数在每个数字中出现的次数不超过一次。现在请注意，我们只能从相同数字的乘积中得到完美的平方。对于在数组中出现n次的数字，我们得到n\xc3\x97(n-1)/2 个完全平方数。找出每个数字在数组中出现的次数作为读者的练习。

\n