素因数分解实现唯一幂集合时的重复元素判定问题求助

大家好，我是个编程新手，最近卡在了一个问题上：我想用素因数分解的方式生成唯一的幂集合，但发现数值完全相同的幂会被集合判定为不同元素。

举个例子，2^4**和**42的数值是相等的，但我的素因数分解结果分别输出成2^2 2^2和2^4，这样存入set<vector<pair<int, int>>>时就被当成了两个不同的元素，导致最终统计的唯一幂数量出错。

我最初的实现代码如下：

#include <iostream>
#include <vector>
#include <set>
using namespace std;

vector<pair<int, int>> prime_factorization(int n) {
    vector<pair<int, int>> factors;
    while (n % 2 == 0) {
        n /= 2;
        factors.emplace_back(2, 1);
    }
    for (int i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            n /= i;
            factors.emplace_back(i, 1);
        }
    }
    if (n > 2) {
        factors.emplace_back(n, 1);
    }
    return factors;
}

set<vector<pair<int, int>>> unique_powers(int a, int b) {
    set<vector<pair<int, int>>> unique;
    for (int i = 2; i <= a; i++) {
        for (int j = 2; j <= b; j++) {
            vector<pair<int, int>> factors = prime_factorization(i);
            for (pair<int, int>& factor : factors) {
                factor.second *= j;
            }
            unique.insert(factors);
        }
    }
    return unique;
}

int main()
{
    set<vector<pair<int, int>>> s = unique_powers(5, 5);
    for (auto v : s) {
        for (auto p : v) {
            cout << p.first << "^" << p.second << "\t| ";
        }
        cout << endl;
    }
    cout << "Unique powers count: " << s.size();
}

运行这段代码后，当输入a=5、b=5时，输出的唯一幂数量是16，但正确结果应该是15——因为2^4和4^2是同一个数值，不该被重复统计。

我尝试过调整幂的压缩逻辑，但一直没成功。后来终于找到问题所在：最初的素因数分解函数把同一个素数的多次幂拆成了多个独立的<素数,1>对，而不是合并成<素数,总幂次>的形式。

修正后的代码如下，现在可以正确生成唯一的幂集合了：

#include <iostream>
#include <vector>
#include <set>

vector<pair<int, int>> prime_factorization(int n) {
    vector<pair<int, int>> factors;
    if (n % 2 == 0) {
        n /= 2;
        factors.emplace_back(2, 1);
        while (n % 2 == 0) {
            n /= 2;
            factors.back().second += 1;
        }
    }
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0)
        {
            n /= i;
            factors.emplace_back(i, 1);
            while (n % i == 0) {
                n /= i;
                factors.back().second += 1;
            }
        }
    }
    if (n > 2) {
        factors.emplace_back(n, 1);
    }
    return factors;
}

set<vector<pair<int, int>>> unique_powers(int a, int b) {
    set<vector<pair<int, int>>> unique;
    for (int i = 2; i <= a; i++) {
        for (int j = 2; j <= b; j++) {
            vector<pair<int, int>> factors = prime_factorization(i);
            for (pair<int, int>& factor : factors) {
                factor.second *= j;
            }
            unique.insert(factors);
        }
    }
    return unique;
}

int main(int argc, char* argv[]) {
    set<vector<pair<int, int>>> s1 = unique_powers(5, 5);
    cout << "Unique powers: " << s1.size() << endl;
    set<vector<pair<int, int>>> s2 = unique_powers(100, 100);
    cout << "Unique powers: " << s2.size() << endl;
    set<vector<pair<int, int>>> s3 = unique_powers(1000, 1000);
    cout << "Unique powers: " << s3.size() << endl;
}

现在运行修正后的代码，输入a=5、b=5时会得到正确的15个唯一幂，数值相同的幂会被素因数分解成完全一致的形式，从而被集合正确判定为同一个元素。

备注：内容来源于stack exchange，提问作者SuboptimalCoder