AcWing 1381. 阶乘 c++ 题解

爱被打了一巴掌 2021-07-24 11:28 301阅读 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