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

· · 题解

题目传送门

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})。

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

*/