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)%m$

$=(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})

。

CPP

#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;
}
/*

*/

题解：B4268 [朝阳区小学组 2019] nonzero

文章操作

Problem

Solution

Code

相关推荐

评论

题解：B4268 [朝阳区小学组 2019] nonzero