给定一个正整数 nn,请计算 S = 1!+2!+3!+\ldots+n!S=1!+2!+3!+…+n! 的末 66 位(不含前导 00)。x!x! 表示 xx 的阶乘,即 1*2*3*\ldots*x1∗2∗3∗…∗x。 【输入格式】 给定一个正整数 nn,请计算 S = 1!+2!+3!+\ldots+n!S=1!+2!+3!+…+n! 的末 66 位(不含前导 00)。x!x! 表示 xx 的阶乘,即 1*2*3*\ldots*x1∗2∗3∗…∗x。 【输入格式】
时间: 2023-05-28 13:06:20 浏览: 90
输入包含一个正整数 n(1≤n≤1091≤n≤109)。 【输出格式】 输出一个整数,表示 S 的末 66 位。 【输入样例】 5 【输出样例】 874166702539019172 我们可以先算出每个数的末6位,然后再累加。由于一个数的末6位只与它的末3位有关,因此我们可以先预处理出1!到n!的末3位,然后再计算末6位。具体地,我们可以将每个数拆成一个后缀和一个前缀,其中前缀是一个6的倍数,后缀的位数不超过3。那么每个数对应的后缀就是其末3位的阶乘,而前缀只有4种情况,即0,6,12,18。我们可以将1!到n!按照前缀分类,然后对于每种前缀单独计算后缀的乘积,最后再将所有结果累加即可得到答案。时间复杂度为O(logn)。
相关问题
请帮我编写C + +代码题目是给定一个正整数 nn,请计算 S = 1!+2!+3!+\ldots+n!S=1!+2!+3!+…+n! 的末 66 位(不含前导 00)。x!x! 表示 xx 的阶乘,即 1*2*3*\ldots*x1∗2∗3∗…∗x。 【输入格式】 给定一个正整数 nn,请计算 S = 1!+2!+3!+\ldots+n!S=1!+2!+3!+…+n! 的末 66 位(不含前导 00)。x!x! 表示 xx 的阶乘,即 1*2*3*\ldots*x1∗2∗3∗…∗x。
#include <stdio.h>
int main()
{
int n, i, j;
long long ans = 1; // ans 存储最终结果
scanf("%d", &n);
for (i = 1; i <= n; i++) // 依次计算每个数的阶乘
{
for (j = 1; j <= i; j++) // 用乘法计算阶乘
{
ans *= j;
if (ans >= 1e20) // 防止数据溢出,每次乘积超过 1e20 时除以 10
{
ans /= 10;
}
}
while (ans % 10 == 0) // 去除末尾的 0
{
ans /= 10;
}
}
printf("%lld\n", ans % 100000000); // 取末 6 位输出
return 0;
}
输入 n (n>0), 计算 s=1/1!+1/2!+1/3!+⋯+1/n!。
我们可以使用循环来计算 $s=1/1!+1/2!+1/3!+\ldots+1/n!$。在每次迭代中,我们将阶乘的结果相加,并将阶乘的结果除以当前的 $i$ 值。以下是计算过程:
1. 初始化变量 $s=0$,$i=1$。
2. 当 $i\leq n$ 时,执行以下操作:
a. 计算 $f_i=\frac{1}{i!}$。
b. 将 $f_i$ 加到 $s$ 上。
c. 将 $i$ 乘以 $i$,然后减 $1$,得到下一个要计算的阶乘 $i!$。
3. 当 $i>n$ 时,退出循环。
4. 输出结果 $s$。
以下是计算 $s=1/1!+1/2!+1/3!+\ldots+1/n!$ 的 Python 代码:
```python
def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n - 1)
def sum_of_factorials(n):
s = 0
i = 1
while i <= n:
f_i = factorial(i)
s += f_i
i *= i
i -= 1
return s
n = int(input("请输入一个正整数 n: "))
result = sum_of_factorials(n)
print("计算结果为:", result)
```