题目链接
题目描述
这是一个函数实现题。你需要实现一个 factorialOfN 函数，它接受一个非负整数 n 作为参数，计算 n 的阶乘 ()。
由于结果可能非常大，你需要返回最终结果对 取模后的值。
定义:
- 特别地，
平台工作模式:
- 你只需要在给定的函数框架内编写核心逻辑。
- 评测系统会自动调用你的函数并验证结果。
- 你不应该编写
main函数或任何输入/输出代码。
示例:
- 输入:
3(由平台处理) - 你的函数被调用:
factorialOfN(3) - 你的函数应返回:
6(因为,
)
解题思路
这道题的核心是实现一个循环计算阶乘，并在每一步都进行取模操作以防止整数溢出。
-
定义模数: 首先，定义一个常量
MOD，其值为。
-
选择迭代法: 计算阶乘最直接的方法是使用循环（迭代）。从 1 循环到
n，将所有数累乘起来。 -
处理大数和溢出:
- 关键性质: 模运算对于乘法有一个非常重要的性质：
(a * b) % m = ((a % m) * (b % m)) % m。 - 应用: 这意味着我们不需要先计算出完整的阶乘（这个数会非常巨大），然后再取模。我们可以在每一步乘法运算后都立即取模，这样可以保证中间结果始终在一个可控的范围内，不会溢出。
- 数据类型: 尽管我们在每步都取模，但中间的乘积
res * i仍然可能超出int的范围。例如，当res接近MOD(~10^9) 时，再乘以一个较大的i，结果可能会超过int的最大值 (~2*10^9)。因此，为了绝对安全，我们应该使用 64 位长整型 (long longin C++,longin Java) 来存储累乘的结果res。
- 关键性质: 模运算对于乘法有一个非常重要的性质：
-
算法步骤: a. 定义一个长整型变量
res并初始化为1。这同时也正确处理了n=0的情况 () 。 b. 定义模数
MOD = 1000000007。 c. 使用一个循环，从i = 1遍历到n。 d. 在循环内部，更新res：res = (res * i) % MOD;。 e. 循环结束后，res中存储的就是最终结果。 f. 由于函数要求返回int类型，将长整型的res转换成int后返回。
这个方法既高效又安全，是解决此类问题的标准模板。
代码
注意：以下是你需要提交的全部内容，即在牛客网给定的模板中填写的代码。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 计算 n 的阶乘
* @param n int整型
* @return int整型
*/
int factorialOfN(int n) {
long long res = 1;
const int MOD = 1e9 + 7;
for (int i = 1; i <= n; ++i) {
res = (res * i) % MOD;
}
return (int)res;
}
};
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 计算 n 的阶乘
* @param n int整型
* @return int整型
*/
public int factorialOfN (int n) {
long res = 1;
final int MOD = 1_000_000_007; // or (int)1e9 + 7
for (int i = 1; i <= n; i++) {
res = (res * i) % MOD;
}
return (int)res;
}
}
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算 n 的阶乘
# @param n int整型
# @return int整型
#
class Solution:
def factorialOfN(self, n: int) -> int:
res = 1
MOD = 10**9 + 7
for i in range(1, n + 1):
res = (res * i) % MOD
return res
算法及复杂度
- 算法: 迭代、模运算。
- 时间复杂度:
。我们需要一个循环从 1 迭代到
n。 - 空间复杂度:
。我们只使用了少数几个变量来存储结果和模数，没有使用与
n的大小相关的额外空间。
京公网安备 11010502036488号