Codeforces 300E(数学)
2024-09-06 08:09:07
题意：给定k个数字，求最小的正整数n，使得“n的阶乘”是“这k个数字的阶乘的积”的倍数。1<=k<=1e6,数字ai满足1<=ai<=1e7
分析：如果我们能对着k个数字的阶乘的结果分解质因数，那么就可以根据每个质因数的指数来二分最后的答案
问题的关键就是如何分解a1!a2!a3!a4!.....
先可以预处理出1..MAX每个数在式子中出现了多少次（对于ai，也就是1~ai中间所有数字出现次数+1），这可以用差分做
我们知道了cnt[1..MAX]后，接下来就是考虑分解了
我们从大到小枚举每个数字x
如果x是合数，我们可以把x分解成一个质因数和另外一个数的乘积，于是我们可以把x位置的次数加到那两个位置上。并且x位置的次数设为0
如果x是素数，则跳过
那么最后，每个素数对应的出现总次数就算出来了
这样是O(n)的
对于一个数字x的质因数，我们可以在欧拉筛的时候记一下，可以记一下最小的质因数
欧拉筛也是O(n)的
最新文章
- 加速android源码编译
- SEO如何辨别真假Baiduspider
- ElasticSearch已经配置好ik分词和mmseg分词(转)
- ComponentOne Studio for Enterprise 2015 v1 全新发布
- Linux之格式化与挂载
- mysql 快速生成百万条测试数据
- fasterflect-vs-hyperdescriptor-vs-fastmember-vs-reflection/
- 一些常用的IOS开发网站
- 为啥都不用Qt Quick Controls 2呢
- opencv-python 学习笔记1：简单的图片处理
- cocos2d触摸事件处理机制（2.x和3.x变化）
- 关于EsayUI中datagrid重复提交后台查询数据的问题
- 【干货】分享几个写 demo 的思路
- Android WebView那些坑之上传文件
- TreeMap就这么简单【源码剖析】
- iBATIS 深入分析
- springboot入门1
- ZipUtil
- CentOS禁止packagekit离线更新服务的办法
- 前端复制粘贴clipBoard.js的使用