求一篇C++题解,Happy New Year

Question

问题描述
这是一道模板题(自然数幂求和)。
给出n,k,P，求: Sk(n)=∑ni=1 i k
对P取模的值。
输入格式
第一行两个正整数P，Q，分别代表模数和询问组数。
接下来Q行每行两个正整数，分别代表n,k。
输出格式
Q行，每行一个正整数，代表所求的Sk(n)对P取模后的结果。
样例输入
19260817 1
10 3
样例输出
3025

Answer 1

上午好☀️☀️☀️️
本答案参考通义千问

这是一个典型的自然数幂求和问题，要求计算 $ S_k(n) = \sum_{i=1}^{n} i^k \mod P $。由于 $ n $ 和 $ k $ 可以很大（例如达到 $ 10^9 $），直接暴力枚举是不现实的。我们需要使用快速幂算法结合前缀和公式或多项式插值法来高效解决这个问题。

---

📌 问题分析

给定：

• 模数 $ P $
• 询问次数 $ Q $
• 每次询问给出 $ n, k $

要求：

• 计算 $ \sum_{i=1}^{n} i^k \mod P $

---

✅ 解题思路

1. 直接暴力法（仅适用于小数据）

对于较小的 $ n $ 和 $ k $，可以直接用循环计算：

long long pow_mod(long long a, long long b, long long mod) {
    long long res = 1;
    while (b > 0) {
        if (b % 2 == 1)
            res = res * a % mod;
        a = a * a % mod;
        b /= 2;
    }
    return res;
}

long long sum_powers(long long n, long long k, long long P) {
    long long res = 0;
    for (long long i = 1; i <= n; ++i) {
        res += pow_mod(i, k, P);
        res %= P;
    }
    return res;
}

但这种方法时间复杂度为 $ O(Q \cdot n) $，在 $ n $ 很大的情况下会超时。

---

2. 快速幂 + 多项式插值法（推荐）

我们可以通过伯努利数或拉格朗日插值法构造一个多项式，使得该多项式在 $ x = 1, 2, ..., n $ 时等于 $ \sum_{i=1}^{x} i^k $。这样可以将 $ \sum_{i=1}^{n} i^k $ 的计算转化为对一个多项式的求值。

核心思想：

• 对于固定的 $ k $，$ \sum_{i=1}^{n} i^k $ 是一个关于 $ n $ 的 $ k+1 $ 次多项式。
• 所以我们可以预先用前 $ k+2 $ 个点来构造这个多项式，然后通过拉格朗日插值法快速求出 $ n $ 处的值。

---

🔧 具体步骤

步骤一：预处理伯努利数（可选）

如果 $ k $ 较大，可以使用伯努利数来构造求和公式。但这需要复杂的数学推导，适合初学者建议采用拉格朗日插值法。

---

步骤二：使用拉格朗日插值法计算多项式值

拉格朗日插值法公式：

$$ f(n) = \sum_{i=0}^{k} y_i \cdot \prod_{j \neq i} \frac{n - j}{i - j} $$

其中 $ y_i = \sum_{m=1}^{i} m^k $，即前 $ i $ 项的幂和。

---

💡 优化方案（代码实现）

下面是完整的 C++ 实现代码，支持大范围的 $ n $ 和 $ k $，并利用拉格朗日插值法快速求解。

#include <bits/stdc++.h>
using namespace std;

const int MAXK = 1000; // 根据实际最大 k 设置

// 快速幂模运算
long long pow_mod(long long a, long long b, long long mod) {
    long long res = 1;
    while (b > 0) {
        if (b % 2 == 1)
            res = res * a % mod;
        a = a * a % mod;
        b /= 2;
    }
    return res;
}

// 拉格朗日插值法计算 f(n)
long long lagrange_interpolation(long long n, long long k, long long P) {
    long long res = 0;
    for (long long i = 0; i <= k; ++i) {
        long long y_i = 0;
        for (long long j = 1; j <= i; ++j) {
            y_i += pow_mod(j, k, P);
            y_i %= P;
        }

        long long numerator = 1;
        long long denominator = 1;

        for (long long j = 0; j <= k; ++j) {
            if (j != i) {
                numerator = numerator * (n - j) % P;
                denominator = denominator * (i - j) % P;
            }
        }

        // 计算分母的逆元
        long long inv_denominator = pow_mod(denominator, P - 2, P);

        res = (res + y_i * numerator % P * inv_denominator % P) % P;
    }

    return res;
}

int main() {
    long long P, Q;
    cin >> P >> Q;

    for (long long q = 0; q < Q; ++q) {
        long long n, k;
        cin >> n >> k;
        cout << lagrange_interpolation(n, k, P) << endl;
    }

    return 0;
}

---

📌 重点说明

✅ 本方法的关键在于：

• 利用拉格朗日插值法将幂和问题转换为多项式求值问题；
• 通过快速幂加速幂运算；
• 通过模运算逆元（费马小定理）处理除法。

---

✅ 示例说明

样例输入：

19260817 1
10 3

计算： $$ \sum_{i=1}^{10} i^3 = 1^3 + 2^3 + ... + 10^3 = 3025 $$

输出结果为 3025。

---

📝 注意事项

• 若 $ P $ 不是质数，则不能使用费马小定理求逆元，需使用扩展欧几里得算法；
• 如果 $ k $ 非常大（如 $ > 1000 $），可能需要进行优化或使用更高效的数学方法（如伯努利数）；
• 当 $ n \leq k $ 时，直接计算即可。

---

如果你有更多类似题目或者想了解如何用伯努利数解决此类问题，欢迎继续提问！