上海电商设计招聘网站,外贸英文网站建设,大学网站建设的意义,网站制作字体文章目录 一、题目[NOIP2009 普及组] 细胞分裂题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 提示 二、题解1.基本思路#xff1a;2.代码#xff1a; 一、题目
[NOIP2009 普及组] 细胞分裂
题目描述
Hanks 博士是 BT#xff08;… 文章目录 一、题目[NOIP2009 普及组] 细胞分裂题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 提示 二、题解1.基本思路2.代码 一、题目
[NOIP2009 普及组] 细胞分裂
题目描述
Hanks 博士是 BTBio-Tech生物技术领域的知名专家。现在他正在为一个细胞实验做准备工作培养细胞样本。
Hanks 博士手里现在有 N N N 种细胞编号从 1 ∼ N 1 \sim N 1∼N一个第 i i i 种细胞经过 1 1 1 秒钟可以分裂为 S i S_i Si 个同种细胞 S i S_i Si 为正整数。现在他需要选取某种细胞的一个放进培养皿让其自由分裂进行培养。一段时间以后再把培养皿中的所有细胞平均分入 M M M 个试管形成 M M M 份样本用于实验。Hanks 博士的试管数 M M M 很大普通的计算机的基本数据类型无法存储这样大的 M M M 值但万幸的是 M M M 总可以表示为 m 1 m_1 m1 的 m 2 m_2 m2 次方即 M m 1 m 2 M m_1^{m_2} Mm1m2其中 m 1 , m 2 m_1,m_2 m1,m2 均为基本数据类型可以存储的正整数。
注意整个实验过程中不允许分割单个细胞比如某个时刻若培养皿中有 4 4 4 个细胞Hanks 博士可以把它们分入 2 2 2 个试管每试管内 2 2 2 个然后开始实验。但如果培养皿中有 5 5 5 个细胞博士就无法将它们均分入 2 2 2 个试管。此时博士就只能等待一段时间让细胞们继续分裂使得其个数可以均分或是干脆改换另一种细胞培养。
为了能让实验尽早开始Hanks 博士在选定一种细胞开始培养后总是在得到的细胞“刚好可以平均分入 M M M 个试管”时停止细胞培养并开始实验。现在博士希望知道选择哪种细胞培养可以使得实验的开始时间最早。
输入格式
第一行有一个正整数 N N N代表细胞种数。
第二行有两个正整数 m 1 , m 2 m_1,m_2 m1,m2以一个空格隔开即表示试管的总数 M m 1 m 2 M m_1^{m_2} Mm1m2。
第三行有 N N N 个正整数第 i i i 个数 S i S_i Si 表示第 i i i 种细胞经过 1 1 1 秒钟可以分裂成同种细胞的个数。
输出格式
一个整数表示从开始培养细胞到实验能够开始所经过的最少时间单位为秒。
如果无论 Hanks 博士选择哪种细胞都不能满足要求则输出整数 − 1 -1 −1。
样例 #1
样例输入 #1
1
2 1
3样例输出 #1
-1样例 #2
样例输入 #2
2
24 1
30 12样例输出 #2
2提示
【输入输出样例 #1 说明】
经过 1 1 1 秒钟细胞分裂成 3 3 3 个经过 2 2 2 秒钟细胞分裂成 9 9 9个……可以看出无论怎么分裂细胞的个数都是奇数因此永远不能分入 2 2 2 个试管。
【输入输出样例 #2 说明】
第 1 1 1 种细胞最早在 3 3 3 秒后才能均分入 24 24 24 个试管而第 2 2 2 种最早在 2 2 2 秒后就可以均分每试管 144 / 24 1 6 144 / {24}^1 6 144/2416 个。故实验最早可以在 2 2 2 秒后开始。
【数据范围】
对于 50 % 50 \% 50% 的数据有 m 1 m 2 ≤ 30000 m_1^{m_2} \le 30000 m1m2≤30000。
对于所有的数据有 1 ≤ N ≤ 10000 1 \le N \le 10000 1≤N≤10000 1 ≤ m 1 ≤ 30000 1 \le m_1 \le 30000 1≤m1≤30000 1 ≤ m 2 ≤ 10000 1 \le m_2 \le 10000 1≤m2≤10000 1 ≤ S i ≤ 2 × 10 9 1 \le S_i \le 2 \times {10}^9 1≤Si≤2×109。
NOIP 2009 普及组 第三题
二、题解
1.基本思路
看到数据范围暴力做肯定是不行的不难发现细胞的分裂时指数形式的可以表示s[i](1 秒钟可以分裂成同种细胞的个数)的t次方t为多少秒。而试管的个数时m1的m2次方根据唯一分解定理他们的底数都可以分解成质因数之积的形式。由于细胞要平均分入试管中所以试管总数分解后有的质数细胞的分解后也有如果没有的话不能是试管的倍数。第二个需要判断的就是细胞经过t次分裂后分解后包含的试管总数分解后有的质数的幂次一定要大于等于试管总数分解后的质数的幂次。唯一分解定理是在这里学的点击链接即可跳转 唯一分解定理是数论中一个非常重要且实用的定理,这个定理是注意描述的任何一个大于1的自然数 N,如果N不为质数那么N可以唯一分解成有限个质数的乘积NP1a1P2a2P3a3…Pnan这里P1P2P3…Pn均为质数其中指数ai是正整数。 2.代码
#includebits/stdc.h
using namespace std;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl \n
#define int long long
#define repn(i,o,n) for(int io;in;i)
#define rep(i,o,n) for(int io;in;i)
const int N 3e410;
//唯一分解定理是数论中一个非常重要且实用的定理
//任何一个大于1的自然数 N,如果N不为质数那么N可以唯一分解成有
//限个质数的乘积NP1a1P2a2P3a3......Pnan这里P1P2P3......Pn均为质数其中指数ai是正整数。
int p1[N],e1[N],cnt10;//将m1的m2次方拆分成若干质数的乘积
//p1记录质数e1记录质数的幂cnt1记录多少个不同的质数的乘积
int p2[N],e2[N];// 将s[i]拆分成若干质数的乘积
//p2,e2,cnt2功能同上
int n,m1,m2,s[N],t[N],cnt20,temp[N];//记录每个细胞分裂成到满足条件所需要的时间如果n个细胞都为0,说明哪种细胞都不满足条件输出-1void divide1(int n1){for(int i2;i*in1;i){if(n1%i0){p1[cnt1]i,e1[cnt1]0;while(n1%i0){n1/i;e1[cnt1];}}}if(n11)p1[cnt1]n1,e1[cnt1];repn(i,1,cnt1)e1[i]*m2;//幂的乘法前面求的是m1的质数幂之积将m2乘进去即可
// for(int i1;icnt1;i)
// coutp1[i]^e1[i] ;
// coutendl;
}void divide2(int n1){int cnt0;for(int i2;i*in1;i){if(n1%i0){p2[cnt]i,e2[cnt]0;while(n1%i0){n1/i;e2[cnt];}}}if(n11)p2[cnt]n1,e2[cnt];cnt2cnt;
// for(int i1;icnt;i)
// coutp2[i]^e2[i] ;
// coutendl;
}void solve(){cinn;//代表细胞种数cinm1m2;if(m11){cout0;return;}repn(i,1,n)cins[i];divide1(m1);unordered_mapint,int mp;//m1有哪些质数 repn(i,1,cnt1)mp[p1[i]]e1[i];repn(i,1,n){memset(p2,0,sizeof(p2));memset(e2,0,sizeof(e2));divide2(s[i]);//先判断该细胞分离后可不可以均分int num0;repn(j,1,cnt2)if(mp.count(p2[j])){num;}if(num!cnt1) continue;//可以均分求出时间 int time1;while(1){repn(j,1,cnt2)temp[j]e2[j];repn(j,1,cnt2)temp[j]*time;bool flagtrue;repn(j,1,cnt2)if(mp.count(p2[j])temp[j]mp[p2[j]]){flagfalse;//couttemp[j] p2[j]endl;break;}if(flag) break;time; }//couttimeendl;t[i]time;}int ans1LL*132;repn(i,1,n)if(t[i]anst[i])anst[i];if(ans!1LL32)coutansendl;elsecout-1endl;
}signed main(){//IOS;int T1;//cinT;while(T--){solve();}return 0;
}
