AcWing 1381. 阶乘 c++ 题解

爱被打了一巴掌 2021-07-24 11:28 325阅读 0赞

### 1.题目 ###

N 的阶乘（记作 N!）是指从 1 到 N（包括 1 和 N）的所有整数的乘积。

阶乘运算的结果往往都非常的大。

现在，给定数字 N，请你求出 N! 的最右边的非零数字是多少。

例如 5!=1×2×3×4×5=120，所以 5! 的最右边的非零数字是 2。

**输入格式**  
共一行，包含一个整数 N。

**输出格式**  
输出一个整数，表示 N! 的最右边的非零数字。

**数据范围**  
1≤N≤1000  
**输入样例：**  
7  
**输出样例：**  
4

### 2.分析 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]  
观察数据，我们可以发现一个规律，如果一个数`n`的阶乘`n!`的末尾包含`1`个或者多个`0`时，我们可以将末尾为`0`的部分去掉，这样并不影响最后的结果，因为我们要求的是`n!`的最右边的非零数字。

这样我们在求解`n!`的时候不断去判断该数是否可以被`10`整数，如果可以，去除末尾为`0`的位。`(m = n!)`

即 `while(m%10==0) m/=10`

但是这样还是不够的，`n!`还是会很大，会超出`long long`范围，所以这时候就应该考虑只保留它的有效部分，就是给`n!`取末尾的`n`位。

经过验证，`n`取`3`到`6`之间都是可以的。我们保留后三位进行运算。

即 `m%=1000`

### 3.**AC代码** ###

#include<iostream>
    
    using namespace std;
    
    int main()
    { 
    	int n;
    	cin >> n;
    	int m = 1;
    	for (int i = 1; i <= n; i++)
    	{ 
    		m *= i;
    		while (m % 10 == 0) m /= 10;  // 去除末尾为0的位
    		m %= 1000;   //保留后三位
    	}
    	cout << m % 10 << endl;
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/af2e91fda2184d84a1b458f0b30055ac.png

发表评论取消回复

表情：

评论列表（有 0 条评论，325人围观）

还没有评论，来说两句吧...

相关阅读

相关 C++实现大数阶乘

在C++中，long long类型虽然可以表示一个很大的数，但是对于大数阶乘来说是远远不够的，因为大数阶乘的结果位数很多，所以我们可以定义一个大容量数组来存放这个结果的每

素颜马尾好姑娘i/ 2023年10月05日 13:38/ 0 赞/ 23 阅读

相关阶乘

function fn(num) { return(function infn(num) { if (num <= 1

た入场券/ 2023年06月03日 15:59/ 0 赞/ 526 阅读

相关【C】阶乘求和

使用VS2019 ISO C++14 标准 (/std:c++14) 阶乘求和 > 求1+2!+3!+...+20!的和。由于20！值为2432902008176

￡神魔★判官ぃ/ 2023年02月13日 08:09/ 0 赞/ 6 阅读

相关【C】阶乘

使用VS2019 ISO C++14 标准 (/std:c++14) 求一个正整数的阶乘 1.采用for遍历的方式 //求正整数的阶乘 //本练习不涉

快来打我*/ 2023年02月09日 13:14/ 0 赞/ 4 阅读

相关 c语言分数阶乘计算

include <stdio.h>

秒速五厘米/ 2022年06月07日 06:41/ 0 赞/ 302 阅读

相关阶乘

问题描述　　一个整数n的阶乘可以写成n!，它表示从1到n这n个整数的乘积。阶乘的增长速度非常快，例如，13!就已经比较大了，已经无法存放在一个整型变量中；而35!就更大了

雨点打透心脏的1/2处/ 2022年04月10日 06:42/ 0 赞/ 302 阅读

相关 c语言计算大数阶乘

问题描述　　输入一个正整数n，输出n!的值。　　其中n!=1\2\3\…\n。算法描述　　n!可能很大，而计算机能表示的整数范围有限，需要使用高精度计算的方法

淩亂°似流年/ 2022年03月18日 06:22/ 0 赞/ 296 阅读

相关阶乘

题目要求：使用while循环计算1+1/2！+1/3！+……+1/20！分析：我们可以观察到的现象：1、分子都为1；2、分母为阶乘表达式，已知阶乘表

墨蓝/ 2021年09月15日 23:14/ 0 赞/ 429 阅读

相关 AcWing 795. 前缀和【c++详细题解】

前缀和 -------------------- 题目输入一个长度为n的整数序列。接下来再输入m个询问，每个询问输入一对l, r。对于每

水深无声/ 2021年09月03日 06:32/ 0 赞/ 440 阅读

相关 AcWing 1381. 阶乘 c++ 题解

1.题目 N 的阶乘（记作 N!）是指从 1 到 N（包括 1 和 N）的所有整数的乘积。阶乘运算的结果往往都非常的大。现在，给定数字 N，请你求出

爱被打了一巴掌/ 2021年07月24日 11:28/ 0 赞/ 326 阅读