P1134 阶乘问题【洛谷算法习题】

P1134 阶乘问题

网页链接

P1134 阶乘问题

题目描述

也许你早就知道阶乘的含义，N NN阶乘是由1 11到N NN相乘而产生，如：

12 ! = 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 × 10 × 11 × 12 = 479,001,600 12!=1\times 2\times 3\times 4\times 5\times 6\times 7\times 8\times 9\times 10\times 11\times 12=479{,}001{,}60012!=1×2×3×4×5×6×7×8×9×10×11×12=479,001,600

12 1212的阶乘最右边的非零位为6 66。

写一个程序，计算N ( 1 ≤ N ≤ 5 × 10 7 ) N\ (1\le N\le5\times 10^7)N(1≤N≤5×107)阶乘的最右边的非零位的值。

注意：10,000,000 ! 10{,}000{,}000!10,000,000!的末尾有2499999 24999992499999个零。

输入格式

仅一行包含一个正整数N NN。

输出格式

一个整数，表示最右边的非零位的值。

输入输出样例 #1

输入 #1

12

输出 #1

6

说明/提示

USACO Training Section 3.2

解题思路

本题核心是因子抵消+模运算+周期规律求解阶乘最后非零位，适配超大范围数据计算。阶乘末尾的0由因子2和5相乘产生，因此先等量抵消2和5消除末尾0；由于仅需最后一位非零数字，计算全程对10取模，彻底避免大数溢出。利用2的幂次周期规律（2、4、8、6循环），迭代处理n/5的部分，遍历个位数时跳过数字5，结合周期数组快速计算剩余因子的乘积。算法时间复杂度为O(log₅N)，无任何大数运算，极致高效，完美适配N≤5×10⁷的超大规模数据。

总结

核心逻辑：抵消阶乘中的2和5因子消除末尾0，仅保留并计算最后一位非零数字。
关键操作：迭代拆分数字、抵消因子、模10防溢出，利用2的周期规律快速求解。
效率保障：对数级时间复杂度，无冗余计算，轻松处理题目最大数据规模。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vt;typedefpair<ll,ll>pll;constll N=1e5+10;constll p=1e9+7;constll INF=1e18;constll M=2e3+10;ll a[4]={6,8,4,2};intmain(){ll n;cin>>n;ll ans=1;while(n>1){for(ll i=1;i<=n%10;i++){if(i!=5)ans=ans*i%10;}n=n/5;ans=ans*a[n%4]%10;}cout<<ans<<endl;return0;}