立方和模运算问题的C++实现

以下是解决该问题的C++代码： ```cpp #include <iostream> using namespace std; // 定义取模的常量 const int MOD = 9901; // 快速幂函数，用于计算 a^b % MOD long long quickPow(long long a, long long b) { long long res = 1; while (b) { if (b & 1) { res = (res * a) % MOD; } a = (a * a) % MOD; b >>= 1; } return res; } int main() { long long n; cin >> n; // 计算 1 到 n 的和 long long sum; if (n % 2 == 0) { sum = (n / 2) % MOD * ((n + 1) % MOD) % MOD; } else { sum = ((n + 1) / 2) % MOD * (n % MOD) % MOD; } // 根据立方和公式，计算立方和并取模 long long result = quickPow(sum, 2); // 输出结果 cout << result << endl; return 0; } ``` ### 代码解释 1. **快速幂函数 `quickPow`**：该函数用于快速计算 `a^b % MOD` 的值，时间复杂度为 $O(log b)$。 2. **主函数 `main`**： - 首先读取输入的整数 `n`。 - 然后计算 `1` 到 `n` 的和 `sum`，为了避免溢出，在计算过程中进行取模操作。 - 根据立方和公式，将 `sum` 平方，使用快速幂函数计算 `sum^2 % MOD`。 - 最后输出结果。 ### 复杂度分析 - **时间复杂度**：$O(log n)$，主要是快速幂函数的时间复杂度。 - **空间复杂度**：$O(1)$，只使用了常数级的额外空间。 ######[AI问答 | 499点数解答 | 2026-03-29 20:20:02]