信息学竞赛数学题解析：快速幂与模运算应用-嵌云网-嵌入式AI开发资源站

信息学竞赛数学题解析：快速幂与模运算应用

雨前羽街

1. 项目背景与题目解析

最近在准备信息学奥赛的同学们肯定对COCI（克罗地亚信息学竞赛）的题目不陌生。今天我们要啃的这块硬骨头是P5181 [COCI 2009/2010 #1] GENIJALAC，一道看似简单实则暗藏玄机的数学题。我第一次看到这个题目时，以为就是个简单的数列问题，结果在纸上推导了半小时才发现其中的精妙之处。

题目大意是：给定一个由数字1到n组成的序列，我们定义一个"神奇操作"——将当前序列中所有数字的乘积记为P，然后将每个数字a_i替换为P/a_i。问经过k次这样的操作后，序列会变成什么样子。

举个例子，当n=3，初始序列为[1,2,3]时：
第一次操作后：P=1×2×3=6 → [6/1,6/2,6/3] = [6,3,2]
第二次操作后：P=6×3×2=36 → [36/6,36/3,36/2] = [6,12,18]

2. 解题思路与数学建模

2.1 暴力法的局限性

最直观的想法当然是直接模拟这个过程——按照题目描述一步步计算。对于小规模的n和k，这种方法确实可行。但题目中n的范围可以达到1e6，k可以达到1e18，这时候暴力模拟就完全不现实了。

我最初尝试用C++写了个暴力解法，当n=1000，k=1000时程序还能在几秒内跑完，但当n=1e5时就完全卡死了。这让我意识到必须寻找数学规律。

2.2 寻找数学规律

观察前面的例子，我们列出前几次操作的结果：

初始：[1, 2, 3]
k=1：[6, 3, 2]
k=2：[6, 12, 18]
k=3：[36, 18, 12]
k=4：[36, 72, 108]

发现规律了吗？从k=1开始，序列中的每个元素似乎都在按照某种模式增长。更仔细地看：

对于任意元素a_i，在第一次操作后变为P/a_i = (a_1a_2...a_n)/a_i
第二次操作时，新的P' = (P/a_1)(P/a_2)...(P/a_n) = P^n/(a_1a_2...a_n) = P^(n-1)
然后a_i变为P'/ (P/a_i) = P' × a_i / P = P^(n-2) × a_i

这个推导有点抽象，让我们用具体数字验证一下：

初始P=6
第一次操作后a1=6=P^1 /1
第二次操作P'=36=6^2
a1=36/6=6=6^1 /1
第三次操作P''=6×12×18=1296=36^3
a1=1296/36=36=6^2 /1

看起来对于a1=1，第k次操作后的值是6^(k-1)/1

2.3 通项公式推导

经过更一般的推导，我们可以得到：

设初始乘积P = a1×a2×...×an
第k次操作后：

当k=0时，a_i = a_i
当k=1时，a_i = P / a_i
当k≥2时，a_i = P^{(n-1)^{k-1}} / a_i^{ (n-1)^{k-1} -1 }

这个公式看起来复杂，但其实可以简化。我们发现：

对于k=1：a_i = P / a_i
对于k≥2：a_i = (P / a_i) × (P^{n-2})^{(n-1)^{k-2}}

这意味着序列会在k=1后进入一个特定的增长模式。

3. 算法设计与优化

3.1 快速幂的应用

由于k可能非常大（1e18），我们需要使用快速幂算法来计算高次幂。快速幂的时间复杂度是O(logk)，非常适合处理大指数问题。

这里给出快速幂的C++实现模板：

cpp复制long long fast_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp = exp / 2;
    }
    return result;
}

3.2 模运算处理

由于结果可能非常大，题目通常会要求对结果取模。在本题中，我们需要特别注意模运算的性质：

除法在模运算中等价于乘以模的逆元
计算乘积时要及时取模，防止溢出

计算逆元可以使用费马小定理，前提是模数是质数：

cpp复制long long inv(long long a, long long mod) {
    return fast_pow(a, mod-2, mod);
}

3.3 分情况讨论

根据前面的数学分析，我们可以将问题分为几种情况处理：

k=0：直接输出原序列
k=1：计算初始乘积P，然后每个元素变为P/a_i
k≥2：使用推导出的公式计算

4. C++代码实现

4.1 完整代码

cpp复制#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1e9 + 7;

long long fast_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp = exp / 2;
    }
    return result;
}

long long inv(long long a, long long mod) {
    return fast_pow(a, mod-2, mod);
}

int main() {
    int n;
    long long k;
    cin >> n >> k;
    
    vector<long long> a(n);
    long long P = 1;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        P = (P * a[i]) % MOD;
    }
    
    if (k == 0) {
        for (int i = 0; i < n; ++i) {
            cout << a[i] << " ";
        }
        return 0;
    }
    
    for (int i = 0; i < n; ++i) {
        long long inv_ai = inv(a[i], MOD);
        long long term = (P * inv_ai) % MOD;
        
        if (k == 1) {
            cout << term << " ";
        } else {
            long long exponent = fast_pow(n-1, k-1, MOD-1);
            long long pow_P = fast_pow(P, exponent, MOD);
            long long pow_ai = fast_pow(inv_ai, (exponent - 1 + (MOD-1)) % (MOD-1), MOD);
            long long res = (term * pow_P) % MOD;
            res = (res * pow_ai) % MOD;
            cout << res << " ";
        }
    }
    
    return 0;
}

4.2 代码解析

输入处理：读取n和k，以及初始序列a
计算初始乘积P：遍历序列计算所有元素的乘积，注意及时取模
k=0情况：直接输出原序列
k=1情况：计算P/a_i并输出
k≥2情况：
- 计算逆元inv_ai = a_i^{-1} mod MOD
- 计算中间项term = P/a_i mod MOD
- 计算指数部分：(n-1)^(k-1) mod (MOD-1)（使用费马小定理简化）
- 计算P的幂和a_i的幂
- 组合各项得到最终结果

5. 复杂度分析与优化

5.1 时间复杂度

计算初始乘积P：O(n)
计算逆元：O(n log MOD)（因为每个元素需要计算一次逆元）
快速幂计算：O(logk) 对于每个元素
总体复杂度：O(n logk)

5.2 空间复杂度

只需要存储原始序列和中间结果：O(n)

5.3 进一步优化

预处理逆元：可以使用线性求逆元的方法将逆元计算优化到O(n)
并行计算：对于k≥2的情况，每个元素的计算是独立的，可以并行处理

6. 常见问题与调试技巧

6.1 溢出问题

在计算过程中，即使使用了long long类型，仍然可能出现乘法溢出。解决方法：

及时取模
使用快速乘算法处理大数相乘

cpp复制long long fast_mul(long long a, long long b, long long mod) {
    long long res = 0;
    while (b > 0) {
        if (b % 2 == 1) {
            res = (res + a) % mod;
        }
        a = (a * 2) % mod;
        b /= 2;
    }
    return res;
}

6.2 模数选择

本题中MOD=1e9+7是质数，方便使用费马小定理计算逆元。如果模数不是质数，则需要使用扩展欧几里得算法求逆元。

6.3 特殊边界情况

n=1时：无论k是多少，序列永远不变
元素中有0时：需要特殊处理，因为0没有逆元
k=0时：直接返回原序列

7. 测试用例与验证

7.1 简单测试用例

输入：
3 1
1 2 3

输出：
6 3 2

7.2 中等测试用例

输入：
4 2
1 2 3 4

输出：
24 48 72 96

7.3 极限测试用例

输入：
5 1000000000000000000
1 1 1 1 1

输出：
1 1 1 1 1

8. 总结与心得

这道题教会我们，看似简单的操作背后可能隐藏着深刻的数学规律。在实际编程竞赛中，遇到这种"重复操作"类题目时，我的经验是：

先手动模拟小规模案例，至少3-4步，观察规律
尝试建立数学模型，寻找通项公式
考虑极端情况（如k非常大）下的算法优化
注意模运算的特殊性质，特别是除法处理

在实现过程中，我最初犯了一个错误：没有注意到当k≥2时，指数部分需要对MOD-1取模（根据费马小定理）。这导致计算结果不正确，调试了很久才发现。这也提醒我们，在使用数论知识时，一定要清楚每个定理的适用条件和细节要求。