Moe's CF Life

喵~ 主人你好呀！今天本喵要给你讲解一道非常有趣的数论题哦，是来自 Codeforces 的 1225D - Power Products。这道题呀，就像是帮数字们寻找它们的“天命真子”，让它们相乘之后能成为一个完美的 k 次方数，是不是听起来就很浪漫喵？

别担心，只要跟着本喵的思路走，你一定能轻松掌握它的喵！

题目大意

我们拿到了一串数字 a_1, a_2, ..., a_n，还有一个整数 k。我们的任务呢，就是要找出有多少对 (i, j)，满足 1 ≤ i < j ≤ n，并且它们的乘积 a_i * a_j 恰好等于某个整数 x 的 k 次方，也就是 a_i * a_j = x^k。

举个例子，如果 k=3，a_i=2，a_j=4，那么 a_i * a_j = 8，而 8 = 2^3，所以这就是一对满足条件的组合啦！我们要做的就是把所有这样的组合都数出来，喵~

解题方法

这道题的核心，就在于 a_i * a_j = x^k 这个神奇的等式。我们来把它掰开揉碎了分析一下喵。

一个数如果能表示成 x^k，那它有什么特点呢？根据算术基本定理，任何一个正整数都可以唯一地分解成一堆质数的乘积。比如说 24 = 2^3 * 3^1。

如果 a_i * a_j 是一个完美的 k 次方数，那么把它质因数分解后，每一个质因子的指数都必须是 k 的倍数！

比如说，k=3，a_i = 2^1 * 3^2, a_j = 2^2 * 3^1。它们的乘积就是 (2^1 * 3^2) * (2^2 * 3^1) = 2^(1+2) * 3^(2+1) = 2^3 * 3^3 = (2*3)^3 = 6^3。你看，质因子 2 的指数是 1+2=3，3 的指数是 2+1=3，都是 3 的倍数，所以它们的乘积就是一个立方数。

这给了我们一个绝妙的思路！对于每个数 a_i，我们可以把它进行质因数分解，看看它的每个质因子 p 的指数 e。我们关心的其实不是 e 本身，而是它模 k 的余数，也就是 e % k。

为了让 a_i * a_j 的质因子 p 的总指数 e_i + e_j 成为 k 的倍数，必须满足 (e_i + e_j) % k = 0。这意味着，如果 a_i 的质因子 p 的指数 e_i 模 k 的余数是 r（r = e_i % k），那么 a_j 的质因子 p 的指数 e_j 模 k 的余数就必须是 k - r (如果 r=0，那余数也得是0)。

这样一来，问题就转化成了一个配对游戏，喵！

定义“特征”: 我们可以为每个数字 a_i 定义一个“特征”。这个特征就是它所有质因子 p 和对应的指数模 k 的余数 e % k 的组合。为了简化，我们只记录那些 e % k != 0 的部分。比如 k=3, a_i = 2^4 * 3^3 * 5^1。4 % 3 = 1，3 % 3 = 0，1 % 3 = 1。那么它的特征就可以表示为 {(2, 1), (5, 1)}。
定义“互补特征”: 对于一个特征，我们可以找到它的“互补特征”。如果 a_i 的特征是 {(p, r)}，那么能和它配对的 a_j 就需要有 {(p, k-r)} 这样的特征。对于上面的例子，a_i 的特征是 {(2, 1), (5, 1)}，那它的互补特征就是 {(2, 3-1), (5, 3-1)}，也就是 {(2, 2), (5, 2)}。
计数: 我们可以遍历整个数组。对于每个数 a_i，我们先计算出它的“互补特征”，然后去查一查我们之前已经遇到过多少个数字拥有这个“互补特征”。把这个数量加到我们的总答案里。查完之后，再把 a_i 自己的“特征”记录下来，供后面的数字查询。

为了高效地记录和查询这些“特征”，我们可以使用一个哈希表（在 C++ 中就是 std::map 或者 std::unordered_map），它的键（Key）是“特征”，值（Value）是这个特征出现的次数。

是不是很简单喵？让本喵来给你梳理一下具体的算法步骤吧！

预处理: 为了快速地对数字进行质因数分解，我们可以先用类似筛法的方式预处理出 1 到 10^5 每个数的最小质因子（Smallest Prime Factor, SPF）。
遍历: 遍历输入的 n 个数字 a_1, ..., a_n。
处理当前数字 a_i: a. 对 a_i 进行质因数分解，得到它的“特征” S_i。S_i 是一个 (质数, 指数 % k) 的列表，只包含那些 指数 % k != 0 的项。 b. 根据 S_i 计算出它的“互补特征” S_complement。 c. 在哈希表中查找 S_complement 出现的次数，加到总答案 ans 中。 d. 将 S_i 在哈希表中的计数加一。
输出答案: 遍历结束后，ans 就是我们要求的总对数啦！

题解代码解析

下面是这道题的 C++ 代码，本喵来逐段给你解释一下它是怎么实现我们刚刚的思路的，喵~

cpp

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

const int MAX = 100000;

int main() {
    // 提高一下输入输出效率，喵~
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // --- 预处理：最小质因子筛 (SPF) ---
    // spf[i] 存储 i 的最小质因子
    vector<int> spf(MAX + 1);
    for (int i = 1; i <= MAX; i++) {
        spf[i] = i; // 初始化，每个数的最小质因子是它自己
    }
    for (int i = 2; i * i <= MAX; i++) {
        if (spf[i] == i) { // i 是一个质数
            for (int j = i * i; j <= MAX; j += i) {
                if (spf[j] == j) { // 如果 j 还没被标记过
                    spf[j] = i;    // 那么 i 就是 j 的最小质因子
                }
            }
        }
    }
    
    // --- 核心逻辑：计数 ---
    // M 用来存储每个“特征”出现的次数
    // 特征用 vector<pair<int, int>> 表示，即 {(p1, e1%k), (p2, e2%k), ...}
    map<vector<pair<int, int>>, long long> M;
    long long ans = 0;

    for (int i = 0; i < n; i++) {
        int x = a[i];
        vector<pair<int, int>> signature; // 当前数字的特征

        // --- 分解质因数并计算特征 ---
        int temp = x;
        while (temp > 1) {
            int p = spf[temp]; // 获取最小质因子
            int count = 0;
            while (temp % p == 0) {
                count++;
                temp /= p;
            }
            int exponent_mod = count % k;
            if (exponent_mod != 0) { // 只记录余数不为0的项
                signature.push_back({p, exponent_mod});
            }
        }

        // --- 计算互补特征 ---
        vector<pair<int, int>> comp_signature;
        for (auto &p_exp : signature) {
            comp_signature.push_back({p_exp.first, k - p_exp.second});
        }
        
        // --- 查找配对并更新答案 ---
        // M[comp_signature] 会返回 comp_signature 出现的次数
        // 如果不存在，会默认构造一个 0，非常方便喵~
        ans += M[comp_signature];

        // --- 将当前数字的特征存入 map ---
        M[signature]++;
    }

    cout << ans << '\n';

    return 0;
}

知识点介绍

这道题用到了一些非常基础但重要的数论和算法知识，本喵来给你总结一下：

质因数分解 (Prime Factorization)
- 概念: 算术基本定理告诉我们，任何大于1的自然数，都可以唯一地分解成有限个质数的乘积。这是数论的基石！
- 应用: 题目中判断一个数是否是 k 次方幂，就是通过检查其所有质因子的指数是否都是 k 的倍数。
模运算 (Modular Arithmetic)
- 概念: 就是我们常说的求余数运算。a % k 表示 a 除以 k 的余数。
- 应用: 在这道题里，我们并不关心质因子的具体指数有多大，只关心它除以 k 的余数。 (e_i + e_j) % k == 0 是解题的关键。
最小质因子筛 (Sieve for Smallest Prime Factor)
- 概念: 这是一种高效的预处理方法，是埃氏筛（Sieve of Eratosthenes）的变种。它可以在 O(N log log N) 的时间内预处理出 1 到 N 所有数的最小质因子。
- 应用: 有了 spf 数组，我们就可以在 O(log x) 的时间内对任意数 x 进行质因数分解，比试除法 O(sqrt(x)) 要快得多，对于需要多次分解质因数的题目来说是必备的优化技巧喵。
哈希表 / 映射 (Hash Map / Map)
- 概念: 一种键-值（Key-Value）对的数据结构，可以快速地通过键来存取值。C++ 中的 std::map (基于红黑树) 和 std::unordered_map (基于哈希表) 都是它的实现。
- 应用: 我们用它来存储和查询数字的“特征”。“特征”本身（一个 vector）作为键，出现的次数作为值。这使得我们能高效地完成配对查找。

希望本喵的题解对你有帮助哦，如果还有不懂的地方，随时可以再来问我！喵~

题目大意 ​

解题方法 ​

题解代码解析 ​

知识点介绍 ​

题目大意

解题方法

题解代码解析

知识点介绍