P1134 [USACO3.2]阶乘问题
创始人
2025-05-28 07:16:57
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;
} 相关内容
热门资讯
容芯致远获天使轮融资
2026年5月8日，北京容芯致远科技有限公司（简称“容芯致远”）宣布完成天使轮融资。本轮融资由万利达...
试管期间能运动吗？避开这些坑，...
做试管的姐妹都纠结：不动怕气血差、影响卵泡，动了又怕伤子宫、毁着床，到底该怎么办？其实试管不用“躺平...
原创 今...
2026年5月6日，国内金价算是彻底“凉”了一下，你看那AU9999现货黄金，直接跌到了1013元一...
美国5月消费者信心再创历史新低...
财联社5月8日讯（编辑 牛占林）随着中东战争持续推高能源价格，美国消费者信心本月继续下滑，并再度刷新...
“压高盛一头”！江西一精神病院...
蓝鲸新闻5月8日讯（记者 徐甘甘）5月8日，盛通股份（002599.SZ）一季报引发资本市场热议——...
2026年企业短视频能力升级：...
本篇将回答的核心问题 2026年企业短视频营销面临哪些关键挑战，有效应对策略是什么？ 服务机构的能力...
江西一精神病院炒股炒成上市公司...
红星资本局5月8日消息，近日，上市公司盛通股份（002599.SZ）发布一季报，披露了前十大股东名单...
企业IP打造指南：小公司低成本...
小公司做企业IP，不是为了装门面，而是让客户在没见到你之前，就能通过内容知道你是谁、你解决什么问题、...
官方：赵心童入选世界斯诺克名人...
北京时间5月8日消息，世界斯诺克巡回赛（WST）今日正式公布了2025/26赛季年终奖项及名人堂更新...
小灰熊AI学员王锋：希望能跟上...
35了，老程序员了。 从进入互联网行业到现在，其实已经做了很多年移动端开发。最早那几年，安卓行业发展...
原创 2...
2026年全国两会把稳定房地产市场列为重点工作，政府工作报告明确提出因城施策控增量、去库存、优供给。...
一年翻倍，六年未归——徽商银行...
文：向善财经 今年的港股市场，与A股市场出现了明显的分化。 A股这边，科技板块在AI浪潮中热闹非凡；...
古井贡酒2025：在行业深度调...
以“稳”为底、以“新”为翼。 文/每日财报 杜康 在行业库存高企、价格倒挂的背景下，当多数酒企在为...
好上好8408万收购鼎瑞芯加码...
5月7日晚，好上好(001298.SZ)抛出一份收购公告，拟以8408万元现金收购深圳市鼎瑞芯科技有...
全面大撤离！李嘉诚英国“套现”...
突发，李嘉诚又卖了。 这次，套现了455亿。 金额不少，但更值得关注的是透露着不同寻常的信号。 因为...
油气价格上涨加剧法国一季度贸易...
据新华社，法国海关7日发布的数据显示，受中东局势推高国际油气价格影响，法国今年第一季度贸易逆差扩大至...
昆仑芯启动科创板IPO上市辅导...
5月8日，据证监会官网显示，昆仑芯(北京)科技股份有限公司于2026年5月7日正式启动科创板上市辅导...
贵州茅台酒股份有限公司关于回购...
来源：上海证券报 证券代码：600519 证券简称：贵州茅台 公告编号：临2026-016 贵州茅...
百度昆仑芯启动科创板上市辅导，...
5月8日，证监会官网显示，昆仑芯（北京）科技股份有限公司 （下称“昆仑芯”）于2026年5月7日正式...
滕州信华的承压时刻：罚单、失信...
2026年4月末，滕州信华美元债单日跌近2%，关联方被列“老赖”。半年前，这家AA+城投曾因非市场化...