求n*kⁿ - (n-1)*k的模时结果为负的问题求助

首先，我注意到你的代码里有两个关键问题需要修正：

1. 公式计算逻辑错误 #

你要计算的是 n*kⁿ，但当前循环里的计算方式得到的其实是 (n*k)^n —— 因为你每次循环都先乘k再乘n，循环n次后就变成了 (n*k) 的n次方，这和目标公式完全不符。

正确计算 n*kⁿ mod p 的方式应该是：

• 先计算 kⁿ mod p（循环n次每次乘k）
• 再将结果乘以n，然后对p取模

2. 模运算结果为负的处理 #

当计算 (c - d) mod p 时，即使数学上 c > d，但由于两者都是对p取模后的结果，可能出现 c%p < d%p 的情况，导致减法结果为负。解决这个问题的核心是让结果回到非负的模p范围内：在减法后加上p，再对p取模。这样即使结果为负，加上p后会变成正数，再取模就能得到正确的非负余数。

优化建议：快速幂处理大n值 #

当n达到1e9时，循环n次会严重超时，这时候应该用快速幂算法来计算 kⁿ mod p，时间复杂度从O(n)降到O(log n)，效率提升非常明显。

修正后的完整代码 #

#include <iostream>
using namespace std;

const long long p = 1000000007;

// 快速幂函数：计算 (base^exp) mod mod_val
long long fast_pow(long long base, long long exp, long long mod_val) {
    long long result = 1;
    base %= mod_val; // 先对底数取模，避免溢出
    while (exp > 0) {
        // 如果指数是奇数，将当前底数乘到结果中
        if (exp % 2 == 1) {
            result = (result * base) % mod_val;
        }
        // 底数平方，指数折半
        base = (base * base) % mod_val;
        exp /= 2;
    }
    return result;
}

int main() {
    long long n = 1000000000;
    long long k = 25;

    // 计算 n*k^n mod p
    long long k_pow_n = fast_pow(k, n, p);
    long long c = ((n % p) * k_pow_n) % p;

    // 计算 (n-1)*k mod p
    long long d = (((n - 1) % p) * (k % p)) % p;

    // 计算 (c - d) mod p，确保结果非负
    long long s = (c - d + p) % p;

    cout << s << endl;
    return 0;
}

关键细节说明 #

• 所有乘法操作后都立即取模，避免数值溢出（尤其是当n和k很大时，中间结果会超出普通整数范围，建议用long long类型存储所有变量）
• (c - d + p) % p 是处理负数结果的标准方法：
  • 如果 c >= d，c - d 是正数，加上p后再取模p，结果还是 c - d
  • 如果 c < d，c - d 是负数，加上p后变成 p + (c - d)，这是一个0到p-1之间的正数，取模p后就是正确的余数

内容的提问来源于stack exchange，提问作者Adit Jain