洛谷 P1069 解题报告
P1069 细胞分裂
题目描述
\(Hanks\)博士是\(BT\) (\(Bio-Tech\),生物技术) 领域的知名专家。现在,他正在为一个细胞实验做准备工作:培养细胞样本。
\(Hanks\) 博士手里现在有\(N\)种细胞编号从\(1\)~\(N\),一个第\(i\)种细胞经过\(1\)秒钟可以分裂为\(S_i\)个同种细胞(\(S_i\)为正整数)。现在他需要选取某种细胞的一个放进培养皿,让其自由分裂,进行培养。一段时间以后,再把培养皿中的所有细胞平均分入\(M\)个试管,形成\(M\)份样本,用于实验。\(Hanks\)博士的试管数\(M\)很大,普通的计算机的基本数据类型无法存储这样大的\(M\)值,但万幸的是,\(M\)总可以表示为\(m1\)的\(m2\)次方,即\(M = m_1^{m_2}\),其中\(m_1\),\(m_2\)均为基本数据类型可以存储的正整数。
注意,整个实验过程中不允许分割单个细胞,比如某个时刻若培养皿中有\(4\)个细胞,
\(Hanks\)博士可以把它们分入\(2\)个试管,每试管内\(2\)个,然后开始实验。但如果培养皿中有\(5\)个细胞,博士就无法将它们均分入\(2\)个试管。此时,博士就只能等待一段时间,让细胞们继续分裂,使得其个数可以均分,或是干脆改换另一种细胞培养。
为了能让实验尽早开始,\(Hanks\)博士在选定一种细胞开始培养后,总是在得到的细胞“刚好可以平均分入\(M\)个试管”时停止细胞培养并开始实验。现在博士希望知道,选择哪种细胞培养,可以使得实验的开始时间最早。
输入输出格式
输入格式:
第一行有一个正整数\(N\),代表细胞种数。
第二行有两个正整数\(m1,m2\)以一个空格隔开,即表示试管的总数\(M = m_1^{m_2}\)
第三行有\(N\)个正整数,第\(i\)个数\(S_i\)表示第\(i\)种细胞经过\(1\)秒钟可以分裂成同种细胞的个数。
输出格式:
输出文件 cell.out 共一行,为一个整数,表示从开始培养细胞到实验能够开始所经过的最少时间(单位为秒)。
如果无论 Hanks 博士选择哪种细胞都不能满足要求,则输出整数-1。
本蒟蒻十分不擅长做数学题,于是决定认真对待每一道数学题。
来分析一波,我们需要满足这个式子
- \(m_1^{m_2}|S_i^{q}\)
我们要找到最小的整数\(q\)值
当然,我们不可能把这个乘开看看能否整除,而应该分解质因数比较。
将\(m_1\)分解,对她的质因数\(q_i\)乘以\(m_2\),在看看要多少个\(S_i\)凑到一起去才能搞到比\(q_i*m_2\)还多的质因子\(q_i\),于是对于每个\(S_i\),我们都可以求的她的最小要求数。
取最小的即可。
code:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=30010;
const int inf=0x3f3f3f3f;
int n,m1,m2,cnt=0;
int a[N];//分解m1后质因子的个数
int pre[N],is_pre[N];
void seperate()
{
memset(a,0,sizeof(a));
int i=1,mm=m1;
while(mm&&i<=cnt)
{
while(mm&&mm%pre[i]==0)
{
mm/=pre[i];
a[pre[i]]++;
}
i++;
}
for(int i=1;i<=m1;i++)
a[i]*=m2;
}
int main()
{
memset(is_pre,1,sizeof(is_pre));
cin>>n>>m1>>m2;
for(int i=2;i<=m1;i++)
{
if(is_pre[i])
pre[++cnt]=i;
for(int j=1;pre[j]*i<=m1&&j<=cnt;j++)
{
is_pre[pre[j]*i]=false;
if(i%pre[j]==0) break;
}
}
seperate();
int s,m_min=inf,m_max=0;
for(int i=1;i<=n;i++)
{
int flag=0;
m_max=0;
scanf("%d",&s);
for(int j=2;j<=m1;j++)
if(a[j])
{
if(s%j!=0)
{
flag=1;
break;
}
int cnt=0;
while(s%j==0)
{
cnt++;
s/=j;
}
if(a[j]%cnt==0)
m_max=max(m_max,a[j]/cnt);
else
m_max=max(m_max,a[j]/cnt+1);
}
if(m_max&&!flag&&m_min>m_max)
m_min=m_max;
}
if(m1==1&&n!=0)
{
printf("0\n");
return 0;
}
if(m_min==inf)
cout<<"-1"<<endl;
else
cout<<m_min<<endl;
return 0;
}
2018.4.25
最新文章
- 1Z0-053 争议题目解析512
- scroll、offset和client的区别
- 使用VSTS/TFS搭建iOS持续集成环境
- Laravel Controller中引入第三方类库
- MySql like模糊查询使用详解
- CAD格式DWF嵌入到自己的网页中展示--Autodesk Design Review
- Android Drawable 关于selector中state_pressed=";true";的位置顺序
- 关于alarm函数
- Java ";JSON中无分隔符日期字符串处理";
- hdu 2082 生成函数
- .Net程序员学用Oracle系列(24):数据字典、死锁
- 测试工具——JMeter
- Python数据类型及其方法详解
- 解决在SecurecCRT登录后,发现方向键、backspace(退格键)、delete(删除键)为乱码的问题
- 使用PHPStorm 配置自定义的Apache与PHP环境
- Ubuntu系统下手动释放内存
- 深入迁出mybatis系列
- 安装arcgis10.5不能启动服务的解决方案转
- 各行业最受欢迎的编程语言,硬件最青睐C和C++
- 分块+lazy 或者 线段树+lazy Codeforces Round #254 (Div. 2) E
热门文章
- Java进阶(五十一)必须记住的Myeclipse快捷键
- libevent之Reactor模式
- 【matlab编程】matlab随机数函数
- 计算机编码方式详解(Unicode、UTF-8、UTF-16、ASCII)
- 深度剖析linux内核万能--双向链表,Hash链表模版
- FFMPEG类库打开流媒体的方法(需要传参数的时候)
- C语言获取系统时间的函数
- LeetCode之“动态规划”:Best Time to Buy and Sell Stock I &;&; II &;&; III &;&; IV
- Github 错误合集:Failed connect to github.com:8080 || Failed connect to github.com:443; No error
- Java学习网站大全