【acwing 寒假每日一题（入门组）】day16 阶乘

题目来源：阶乘

题目描述

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

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

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

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

输入格式
共一行，包含一个整数 N。

输出格式
输出一个整数，表示 N! 的最右边的非零数字。

数据范围
1≤N≤1000
输入样例：
7
输出样例：
4

思路

思路就是求出n!末尾有几个0，假设为k，然后n! /10^k 在mod10 就好了

n! /10^k 相当于是在n!中找到k个2*5抵消
那么我们将n!转化为2^a * 5^b *剩余部分就变为了2^a-k * 5^b-k *剩余部分，我们对2^a-k * 5^b-k和剩余部分分别mod10再相乘结果就出来了，但是可能数值太大会爆 我们选择对每个因子操作一次我们上面的操作

取模的性质

(ab)mod c =(a mod c)(b mod c)

代码

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin>>n;
    int res=1,d2=0,d5=0; 
    //res是结果  d2存放n的阶乘的每个元素的因子中2的个数 d5存放n的阶乘的每个元素的因子中5的个数
    for(int i=1;i<=n;i++) //遍历阶乘的每个元素
    {
        int x=i;
        while(x%2==0) x/=2,d2++; //累加因子2的个数
        while(x%5==0) x/=5,d5++; //累加因子5的个数
        res=res*x%10; //按照取模的乘法原理 将剩余部分取模
    }
    int k=min(d2,d5); //2和5组合才会出现0 k表示阶乘结果中末尾0的个数
    
    //按照取模的乘法原理 将2和5取模
    for(int i=0;i<d2-k;i++) res=res*2%10;
    for(int i=0;i<d5-k;i++) res=res*5%10;
    cout<<res<<endl;
    return 0;
}