自动搬运

查看原文

来自洛谷，原作者为

	niuniudundun 天禄

搬运于2025-08-24 21:18:14，当前版本为作者最后更新于2025-03-24 17:57:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

Problem

求出 $n!$ 的最后面的非零位是多少。

Solution

首先如何将 $n!$ 的最后一位算出？

推论：对于加法、乘法、乘方运算，算好后取余和边算边取余是等价的。

证明：

以加法为例：

$(a+b+c+\cdots +d)\bmod m$

将 $a,b,c,\cdots ,d$ 分解成 $z_1m+k_1,z_2m+k_2,z_3m+k_3\cdots z_4m+k_4$。

则原式：

$=(z_1m+k_1 , z_2m+k_2 , z_3m+k_3+\cdots +z_4m+k_4)%m$

$=(k_1+k_2+k_3+\cdots +k_4)$

$=(a\bmod m+b\bmod m+c\bmod m+\cdots +d\bmod m)$

乘法也是类似。

随后就是将 $n!$ 的零位去除，可以不断将 $n!\bmod 10$ 如果是 $0$ 则去除它，也就是 $n{\div} 10$。

如果你按上面的步骤并且开 unsigned long long，你只能得 $30$ 分。这时你需要设一个值最好是 $10$ 的次方，不断将 $n\bmod$ 这个值，可以减少复杂度。这里我使用 $10^4$。

Code

复杂度：$O(\frac{n\log_{10}n}{10^4})$。

#include<bits/stdc++.h>
using namespace std;
unsigned long long n,sum=1;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		sum*=i;
		while(sum%10==0){
			sum/=10;
		}
		sum%=10000;
	}
	cout<<sum%10<<endl;
	return 0;
}
/*

*/