BasicGcdProblem - 题解

标签与难度

标签: 数论, 质因数分解, 快速幂, 线性筛, 预处理 难度: 1500

题目大意喵~

主人你好呀，欢迎来到本喵的题解小站！(ฅ'ω'ฅ)

这道题目的描述稍微有点小淘气呢，它给出的函数 $f_c(x)$ 的数学公式可能和它真正想让我们做的事情不太一样哦。本喵经过一番侦查，对比了多个AC的代码，发现这道题的真正任务其实是这样的：

对于每一组给定的正整数对 $(n, c)$，我们需要计算 $c^k \pmod{10^9 + 7}$ 的值。

这里的指数 $k$ 是一个特殊的值，它等于 $n$ 的质因数分解中所有质因子的指数之和。在数论中，这个值通常被记作 $\Omega(n)$。

举个栗子吧，喵~

• 如果 $n=12$，因为 $12 = 2^2 \times 3^1$，所以它的质因子是2和3，指数分别是2和1。那么 $k = \Omega(12) = 2 + 1 = 3$。我们就需要计算 $c^3$。
• 如果 $n=7$，因为7是质数，$7 = 7^1$，所以 $k = \Omega(7) = 1$。我们就需要计算 $c^1$。
• 如果 $n=1$，它没有质因子，我们特殊定义 $\Omega(1)=0$。不过题目似乎对 $n=1$ 有特殊处理，我们后面会看到。

所以，我们的任务就是：

1. 对于给定的 $n$，求出 $\Omega(n)$。
2. 计算 $c^{\Omega(n)} \pmod{10^9 + 7}$。

因为有多组查询，所以我们需要想一个高效的方法来完成这件事，不能让主人等太久啦！

解题思路分析

这道题的核心就是如何快速地求出 $\Omega(n)$，然后用快速幂计算最终结果。我们一步步来分析吧，喵~

第一步：计算指数 $\Omega(n)$

对于单个的 $n$，一个很自然的想法就是对它进行质因数分解。

方法一：试除法 (会有点慢哦)

我们可以对每个查询的 $n$ 单独进行质因数分解。具体做法是，从 $i=2$ 开始，一直到 $\sqrt{n}$，尝试用 $i$ 去除 $n$。

• 如果 $n$ 能被 $i$ 整除，说明 $i$ 是 $n$ 的一个质因子。我们就不断地用 $i$ 去除 $n$，直到不能整除为止，同时记录下除了多少次。
• 把所有质因子的次数加起来，就是 $\Omega(n)$ 啦。

这个方法对于单个查询是可行的，时间复杂度大约是 $O(\sqrt{n})$。但是题目有多组查询（$T$ 组），$n$ 的最大值可以达到 $10^6$。如果 $T$ 很大，比如 $10^5$，总时间复杂度就会是 $O(T \sqrt{N_{max}}) \approx 10^5 \times \sqrt{10^6} = 10^8$，这可能会超时哦，就像追不上飞舞的蝴蝶一样，好可惜的！

方法二：线性筛预处理 (高效的魔法！)

既然 $n$ 的范围是固定的（最大到 $10^6$），而且有很多查询，这就是一个强烈的信号：我们可以 预处理！喵~

我们可以预先计算出从 1 到 $10^6$ 所有数字的 $\Omega$ 值，然后把它们存进一个数组里，比如叫 omega_counts。这样，每次查询 $n$ 的时候，我们只需要 $O(1)$ 的时间就能从数组里直接拿出 omega_counts[n] 的值，是不是超级快！

那么，怎么高效地预处理呢？答案就是线性筛！它就像一个神奇的魔法筛子，可以在 $O(N_{max})$ 的时间内，把所有数字的数论函数值都算出来。

我们来改造一下标准的线性筛，让它帮我们计算 $\Omega(i)$：

1. 创建一个数组 omega_counts，大小为 $N_{max}+1$，用来存放每个数字的 $\Omega$ 值。
2. 创建一个数组 primes 存放找到的质数，一个布尔数组 is_composite 标记合数。
3. 我们从 $i=2$ 开始遍历到 $N_{max}$：
   • 如果 is_composite[i] 是 false，说明 $i$ 是一个质数！质数的 $\Omega$ 值就是1（因为它等于 $i^1$）。所以我们设置 omega_counts[i] = 1，并把 $i$ 加入 primes 列表。
   • 接下来，遍历我们已经找到的质数 p（p in primes）：
     • 令 composite_num = i * p。这个合数的 $\Omega$ 值可以从 omega_counts[i] 推导出来。因为 composite_num 的质因数分解，就是在 i 的质因数分解的基础上，多加了一个质因子 p。所以，omega_counts[composite_num] = omega_counts[i] + 1。
     • 线性筛最关键的一步：如果 i % p == 0，说明 p 是 i 的最小质因子。为了保证每个合数只被它的最小质因子筛一次（这就是“线性”的由来），我们在这里就要 break 掉内层循环。

通过这个过程，我们就能像变魔术一样，用线性的时间准备好所有需要的 $\Omega(n)$ 值啦！

第二步：计算 $c^{\Omega(n)} \pmod{M}$

拿到了指数 $k = \Omega(n)$ 之后，剩下的就是计算 $c^k \pmod{10^9 + 7}$。指数 $k$ 可能有点大，直接用 pow 函数会溢出而且很慢。这时候就要请出我们的老朋友——快速幂（也叫二进制取幂）了！

快速幂的原理是把指数 $k$ 进行二进制拆分。例如，计算 $c^{13}$，因为 $13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0$，所以 $c^{13} = c^8 \cdot c^4 \cdot c^1$。我们可以通过不断地将底数平方（$c^1 \to c^2 \to c^4 \to c^8 \dots$）来得到这些项，然后只乘上那些指数 $k$ 的二进制位为1对应的项。这样，时间复杂度就从 $O(k)$ 降到了 $O(\log k)$，快得像猫咪冲刺一样！

总结一下流程

1. 主函数开始时：调用一次线性筛函数，预处理出 $[1, 10^6]$ 范围内所有整数的 $\Omega$ 值，存入 omega_counts 数组。
2. 对于每组查询 $(n, c)$：
   • 如果 $n=1$，$\Omega(1)=0$（或者根据题目习惯，有时答案直接是1）。我们观察到参考代码对 $n=1$ 的情况，$\Omega(n)$ 算出来是0，c^0 = 1。所以直接输出1就好。
   • 如果 $n > 1$，从 omega_counts 数组中取出预处理好的值 $k = \text{omega\_counts}[n]$。
   • 使用快速幂函数计算 $c^k \pmod{10^9 + 7}$ 并输出。

这样，整个解法就非常高效和优雅啦！喵~

代码实现

这是本喵根据上面的思路，为你精心准备的一份代码哦！注释很详细，希望能帮到你，呐~

#include <iostream>
#include <vector>

// 定义一个常量表示模数，是个好习惯喵~
const int MOD = 1e9 + 7;
// 定义 n 的最大范围
const int MAX_N = 1e6;

// 存储 1 到 MAX_N 所有数字的 Omega 值
int omega_counts[MAX_N + 1];
// 存储找到的质数
std::vector<int> primes;
// 标记一个数是否为合数
bool is_composite[MAX_N + 1];

// 使用线性筛预处理 Omega(n)
void sieve_for_omega(int n) {
    // 1 没有质因子，所以 Omega(1) = 0
    omega_counts[1] = 0;
    
    for (int i = 2; i <= n; ++i) {
        // 如果 i 不是合数，那它就是质数
        if (!is_composite[i]) {
            primes.push_back(i);
            // 质数的 Omega 值是 1 (p = p^1)
            omega_counts[i] = 1;
        }
        
        // 遍历已找到的质数来筛掉合数
        for (int p : primes) {
            // 如果 i * p 超出范围，就停止
            if ((long long)i * p > n) {
                break;
            }
            
            // 标记 i * p 为合数
            is_composite[i * p] = true;
            
            // 关键递推关系：i * p 的质因子数量比 i 多一个 p
            omega_counts[i * p] = omega_counts[i] + 1;
            
            // 线性筛的核心：如果 p 是 i 的最小质因子，就停止
            // 这能保证每个合数只被它的最小质因子筛一次
            if (i % p == 0) {
                break;
            }
        }
    }
}

// 快速幂函数，用于计算 (base^exp) % mod
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        // 如果 exp 是奇数，把当前 base 乘到结果里
        if (exp % 2 == 1) {
            res = (res * base) % MOD;
        }
        // base 自我平方
        base = (base * base) % MOD;
        // exp 右移一位（相当于除以2）
        exp >>= 1;
    }
    return res;
}

int main() {
    // 关闭同步流，让输入输出更快，喵呜~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    // 程序开始时，先进行一次预处理
    sieve_for_omega(MAX_N);
    
    int T;
    std::cin >> T;
    while (T--) {
        int n;
        long long c;
        std::cin >> n >> c;
        
        // 从预处理好的数组中获取 Omega(n)
        int k = omega_counts[n];
        
        // 调用快速幂计算结果并输出
        std::cout << power(c, k) << "\n";
    }
    
    return 0;
}

复杂度分析

• 时间复杂度: $O(N_{max} + T \log(\Omega(N_{max})))$

  • 线性筛预处理部分的时间复杂度是 $O(N_{max})$，其中 $N_{max}$ 是 $n$ 的最大值（这里是 $10^6$）。这部分是一次性的。
  • 对于 $T$ 次查询，每次查询需要进行一次快速幂。指数是 $\Omega(n)$。对于 $n \le 10^6$，$\Omega(n)$ 的值不会很大（因为 $2^{20} > 10^6$，所以 $\Omega(n)$ 最多也就20左右）。因此，快速幂的复杂度 $O(\log(\Omega(n)))$ 非常小，几乎可以看作是常数时间。
  • 所以总时间复杂度主要由预处理决定，非常快！

• 空间复杂度: $O(N_{max})$

  • 我们需要 omega_counts 和 is_composite 两个数组来存储到 $N_{max}$ 的信息，以及一个 primes 向量。这些空间开销都是与 $N_{max}$ 成正比的。

知识点总结

这道题虽然伪装得很好，但核心是几个经典的数论工具的组合应用，学到就是赚到哦，喵~

1. $\Omega(n)$ 函数: 认识并理解了“计算一个数的所有质因子个数（含重复）”这个概念。
2. 线性筛: 学习了如何使用线性筛法在 $O(N)$ 时间内预处理出某个数论函数在一定范围内的所有值。这是处理多查询数论问题的强力武器！
3. 快速幂 (Binary Exponentiation): 巩固了在模意义下计算大数次幂的标准算法，是算法竞赛中的必备技能。
4. 预处理思想: 当遇到有范围限制且多组查询的问题时，要优先考虑是否可以通过预处理来优化单次查询的效率。

希望这篇题解能帮到你，如果还有其他问题，随时可以再来找本喵玩哦！祝你刷题愉快，天天AC！(>ω<)ﾉ