数组完美对数量计算问题及算法错误排查求助

问题描述 #

给定包含N个整数的数组A，若索引对(i,j)（i<j）对应的元素乘积为完全平方数（某整数与自身相乘得到的正整数），则称其为“完美对”。需找出数组A中的完美对总数。

我的思路与问题 #

我尝试用哈希表统计数组元素的出现次数来解决：

• 用公式 (元素出现次数*(次数-1))/2 计算相同元素组成的完美对（如[3,3,3]可形成3对）
• 统计1与完全平方数组成的完美对
  但该方法在部分测试用例中结果错误，不清楚原因。

我的代码实现 #

#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;
}

问题分析 #

你的代码只覆盖了两种有限的场景，完全遗漏了大量合法的完美对，这是导致测试用例出错的核心原因：

1. 遗漏不同元素的合法配对：比如[2,8]的乘积是16（完全平方数），但你的代码不会统计这对；再比如[3,12]的乘积是36（完全平方数），也不会被统计。
2. 逻辑仅覆盖表面场景：你只考虑了相同元素、1与平方数的配对，但没有抓住“乘积为完全平方数”的本质条件。

核心原理 #

两个数的乘积为完全平方数的充要条件是：它们的平方自由形式完全相同。

• 平方自由形式：将数分解质因数后，每个质因数的次数取模2，仅保留次数为奇数的质因数，相乘得到的结果。例如：
  • 8 = 2³ → 2（3 mod 2 = 1，保留2）
  • 2 = 2¹ → 2（1 mod 2 =1，保留2）
  • 12 = 2²×3¹ →3（2的次数为偶数舍去，3的次数为奇数保留）
  • 4=2² →1（所有质因数次数为偶数，结果为1）
  • 1的平方自由形式为1

只要两个数的平方自由形式相同，它们的乘积必然是完全平方数（所有质因数次数均为偶数）。

修正后的解法 #

思路 #

1. 对每个数计算其平方自由形式（注意处理负数：负数只能和负数配对，因为正数×负数结果为负，无法成为正的完全平方数）
2. 用哈希表统计每个平方自由形式的出现次数
3. 对每个平方自由形式的出现次数k，贡献k*(k-1)/2个完美对（任意两个该形式的数均可组成完美对）

修正代码 #

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>

using namespace std;

// 计算数的平方自由形式
int getSquareFree(int x) {
    if (x == 0) return 0; // 0的乘积不是正完全平方数，跳过
    bool isNegative = false;
    if (x < 0) {
        isNegative = true;
        x = -x;
    }
    int res = 1;
    // 分解质因数，保留次数为奇数的质因数
    for (int i = 2; i * i <= x; ++i) {
        int cnt = 0;
        while (x % i == 0) {
            cnt++;
            x /= i;
        }
        if (cnt % 2 != 0) {
            res *= i;
        }
    }
    // 处理剩余的质因数
    if (x > 1) {
        res *= x;
    }
    // 负数的平方自由形式取负，确保仅与负数配对
    return isNegative ? -res : res;
}

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
    unordered_map<int, int> freq;
    long long cnt = 0; // 使用long long避免计数溢出
    for (int num : v) {
        int sf = getSquareFree(num);
        if (sf == 0) continue; // 跳过0
        // 累加当前已有的相同平方自由形式的数量，再更新频率
        cnt += freq[sf];
        freq[sf]++;
    }
    cout << cnt << endl;
    return 0;
}

测试用例验证 #

• 测试用例[2,8]：修正代码返回1，符合预期
• 测试用例[3,12,3]：修正代码返回3（3&3、3&12、3&12），符合预期
• 测试用例[1,4,16]：平方自由形式均为1，出现次数3，贡献3×2/2=3对，符合预期

内容的提问来源于stack exchange，提问作者Sleepy Tinker