寒假打卡——AcWing1381. 阶乘

2021-01-24

1381. 阶乘

题意

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

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

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

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

思路
因式分解:

思路很简单:对原阶乘式子进行因式分解,即质因子的个数,容易发现末尾为0的肯定是2*5得到的,
我们将a[2]和a[5]均减掉min(a[2],a[5]),这样按质因子算的阶乘的时候只用保留最右边一个数即可,末尾不会出现0的情况了。

代码

#include<bits/stdc++.h>

using namespace std;

const int N=1005;

int a[N];

int main()
{
    int n;
    cin>>n;

    for(int i=1;i<=n;i++) {
        int x=i;
        for(int j=2;j<=x;j++) {
            if(x%j==0) {
                int cnt=0;
                while(x%j==0) {
                    cnt++;
                    x/=j;
                }
                a[j]+=cnt;
            }
        }
        if(x)   a[x]++;
    }

    int temp=min(a[2],a[5]);
    a[2]-=temp;
    a[5]-=temp;
    /*
    for(int i=2;i<=10;i++) {
        cout<<a[i]<<' ';
    }
    puts("");
    */
    long long int k=1;
    for(int i=2;i<=n;i++) {
        long long int x=1;
        while(a[i]) {
            x*=i;
            x%=10;
            a[i]--;
        }
        k*=x;
        k%=10;
    }

    cout<<k<<'\n';
    return 0;

}

标题:寒假打卡——AcWing1381. 阶乘
作者:xiaob0
地址:https://xiaobo.net.cn/articles/2021/01/24/1611475353471.html