bdfz_2024_summer/day7/P5431/chat.md

以下是上述问题的 C++ 实现代码，使用了快速幂计算逆元和高效的 IO 处理方式，以应对可能的大规模数据输入。

C++ 实现

#include <iostream>
using namespace std;

// 快速幂计算 (base^exp) % mod
long long mod_exp(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 /= 2;
    }
    return result;
}

// 模逆元计算: a^(p-2) % p
long long mod_inverse(long long a, long long p) {
    return mod_exp(a, p - 2, p);
}

int main() {
    ios::sync_with_stdio(false);  // 提高cin/cout的效率
    cin.tie(0);  // 取消cin与cout的关联

    int n;
    long long p, k;
    cin >> n >> p >> k;

    long long result = 0;
    long long k_power = 1;  // k^i

    for (int i = 0; i < n; ++i) {
        long long a_i;
        cin >> a_i;

        long long inv_a = mod_inverse(a_i, p);
        long long term = (k_power * inv_a) % p;
        result = (result + term) % p;
        
        // 更新k_power
        k_power = (k_power * k) % p;
    }

    cout << result << endl;
    return 0;
}

代码解释

1. 快速幂函数 mod_exp：通过二进制分解指数，实现快速计算幂次取模。
2. 模逆元函数 mod_inverse：利用费马小定理，通过快速幂计算模逆元。
3. 高效的输入输出：
   • ios::sync_with_stdio(false) 关闭 C++ 的 IO 与 C 的 IO 之间的同步，提高 IO 效率。
   • cin.tie(0) 解除 cin 与 cout 的关联，避免在每次 cin 之前执行 cout，进一步提升效率。
4. 主函数逻辑：
   • 读取输入的 n, p, k，以及数组 a_i。
   • 逐步计算每个 k^i \times a_i^{-1} \mod p 并累加到结果中。
   • 最终输出累加结果。

样例测试

使用样例输入：

6 233 42
1 4 2 8 5 7

程序将输出：

91

性能优化

在 n 非常大的情况下，使用上述 C++ 实现，可以确保在合理时间内完成计算。此实现充分利用了快速幂和费马小定理的性质，以及 C++ 的高效输入输出特性。