P1134 [USACO3.2]阶乘问题
创始人
2025-05-28 06:23:14
0次

题面：

解题：

long long？高精？储存50,000,000！？ NO！NO！NO！

如此的空间复杂度、时间复杂度都不太能扛得住。

排除了暴力做法，结合题目来分析：

  • 假如两个数相乘后不产生0，那么乘积的个位即所求第一个非零元素，

因此，每次相乘后，我们只需要对结果保留个位即可，即%10，因此不用担心数据溢出；

0产生的原因

  • 一方面有例如10、200、3000这样整十整百的数，而末尾的0对非零位没有影响，我们需要把其末尾0全部删掉，取非零位的第一个元素即可；

  • 另一方面，5×2也能得到0，不妨把所有乘数中的2、5全部提取出来，

而2的产生速率远远大于5，因此，在最后，我们将所有5与2配对，再将答案乘上剩下的2即可

AC代码奉上

#include
#include
#include
using namespace std;long long n, fiveIndex = 0, twoIndex = 0, ans = 1;int main()
{cin >> n;for (int i = 1; i <= n; i++){int temp = i;while (temp % 10 == 0)temp /= 10; //末尾的0不参与乘法运算while (temp % 5 == 0) //记录5的个数{temp /= 5;fiveIndex++;}while (temp % 2 == 0) //记录2的个数{temp /= 2;twoIndex++;}ans *= temp;ans %= 10;//自信保留个位即可}int round = (twoIndex - fiveIndex) % 4;int condition[4] = { 6,2,4,8 }; //乘1,2,3,4次2位数分别为2/4/8/6ans *= condition[round];cout << ans % 10 << endl;return 0;
}
词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：MongoDB详解，用心看这篇就够了【重点】

下一篇：vue2 ant-design记忆表头列表页面组件

相关内容

热门资讯

安卓如何操控苹果系统,揭秘跨平... 你知道吗？在这个科技飞速发展的时代，安卓和苹果两大操作系统之间的较量可是从未停歇。虽然它们各自有着忠...
安卓系统账户同步数据,畅享无缝... 你有没有遇到过这种情况：手机里存了那么多宝贝照片、重要文件，结果换了个新手机，却发现那些宝贝全都不翼...
安卓系统不停推送广告,安卓系统... 你有没有发现，最近你的安卓手机是不是越来越“热情”了？没错，就是那个不停在你屏幕上跳来跳去的广告！今...
airpods可以和安卓系统,... 你有没有想过，那些炫酷的AirPods竟然也能和安卓手机完美搭配？没错，就是那个我们平时只听说和iP...
安卓系统实体键盘不对,创新与挑... 你是不是也遇到了这个问题？安卓手机的实体键盘突然不对劲了，按下去没反应，或者反应迟钝，简直让人抓狂！...
汽车导航改装安卓系统,安卓系统... 你有没有想过，你的汽车导航系统是不是已经out了？现在，让我来给你揭秘如何给你的爱车来一次科技大变身...
安卓系统如何限制下载,安卓系统... 你有没有发现，手机里的安卓系统越来越智能了？不过，这也意味着有时候我们不小心就会下载一些不想要的软件...
安卓系统调成日语,概要の副標題... 你有没有想过，你的安卓手机竟然可以变成一个日式小天地呢？没错，就是那种动漫里常见的日语界面，是不是听...
男生耳机推荐安卓系统,男生耳机... 耳机可是现代生活中不可或缺的小玩意儿，尤其是对于喜欢听音乐的男生来说，一副好耳机简直就是灵魂的伴侣。...
安卓同版本升级系统,功能优化与... 你知道吗？最近手机界可是热闹非凡呢！各大品牌纷纷推出了安卓同版本升级系统，让我们的手机焕然一新。今天...
安卓更换别的手机系统,轻松切换... 你有没有想过，你的安卓手机用久了，是不是有点审美疲劳了呢？或者，你最近是不是对其他手机系统产生了浓厚...
安卓系统单机神雕侠侣,指尖重温 你有没有想过，在手机上也能体验一把江湖恩怨、侠骨柔肠？没错，就是那个让人心驰神往的《神雕侠侣》！今天...
安卓系统键盘语言切换,安卓系统... 你有没有发现，手机上的安卓系统键盘语言切换功能，简直就像是个神奇的魔法棒，轻轻一点，就能让文字飞舞在...
oppok1安卓系统,性能与体... 你有没有发现，最近手机圈里又掀起了一股热潮？没错，就是OPPO K1这款新机！这款手机不仅外观时尚，...
安卓系统环境的搭建,从零开始构... 想要在电脑上体验安卓系统的魅力，是不是已经跃跃欲试了呢？别急，今天就来手把手教你如何搭建一个属于自己...
【MySQL】锁 锁 文章目录锁全局锁表级锁表锁元数据锁（MDL）意向锁AUTO-INC锁...
【内网安全】 隧道搭建穿透上线... 文章目录内网穿透-Ngrok-入门-上线1、服务端配置：2、客户端连接服务端ÿ...
GCN的几种模型复现笔记 引言 本篇笔记紧接上文，主要是上一篇看写了快2w字，再去接入代码感觉有点...
数据分页展示逻辑 import java.util.Arrays;import java.util.List;impo...
Redis为什么选择单线程？R... 目录专栏导读一、Redis版本迭代二、Redis4.0之前为什么一直采用单线程？三、R...