题解 | 阶乘末尾非零数字

#include<bits/stdc++.h>
using namespace std;

using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using u128=__uint128_t;
using ld=long double;

void solve()
{//我们想要知道 阶乘的从右往左数第一个非零数字 那么 我们肯定要关注n!的最后几位数 那么n!的最后几位数可以通过如下方法获得
//直接模拟计算n!的过程 每一步都乘上当前的数 然后去掉末尾所有的0 并保留足够多的低位数字 即mod上一个大数 如1e6
//这样既能保证后续乘法中进位信息的正确传递 又能控制数字范围在1e18内 最后输出结果的个位数即可
//多提一嘴 有人可能会想 我只在个位上进行乘法不就好了 每次结果再保留个位 如果可以mod10 则保留十位
//这种想法其实是错的 因为一个数字和另一个数字相乘的第一个非零数字的数值 不仅来自于它本身的个位乘另外一个数 还来自高位乘法向低位的进位 所以 我们要保留足够的有效数字 防止位数不够 得到错误答案
	ll n,ans=1;
	cin >> n;
	for(ll i=1;i<=n;i++)
	{
		ans=ans*i;

		while(ans%10==0) ans/=10;
		
		ans%=1000000;
	}
	cout << ans%10;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t=1;
	//cin >> t;
	
	while(t--)
	{
		solve();
	}
	return 0;
}