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

张开发
• 2026/4/10 14:06:43 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

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 12479{,}001{,}60012!1×2×3×4×5×6×7×8×9×10×11×12479,001,60012 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输入 #112输出 #16说明/提示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的周期规律快速求解。效率保障对数级时间复杂度无冗余计算轻松处理题目最大数据规模。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N1e510;constll p1e97;constll INF1e18;constll M2e310;ll a[4]{6,8,4,2};intmain(){ll n;cinn;ll ans1;while(n1){for(ll i1;in%10;i){if(i!5)ansans*i%10;}nn/5;ansans*a[n%4]%10;}coutansendl;return0;}

更多文章