haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 学科竞赛学科竞赛

NOIP2009 细胞分裂

发布时间:2014-01-07 12:43:55  

题意抽象出来就是求(cell[i])^k mod m1^m2=0的最小的k值。

把m1^m2分解质因数即可,再把每一个细胞数分解,对比其质因子数量,对于某个因子,m1^m2次有而后者没有,那么这种情况一定无解,继续枚举下一个细胞数即可,而两者都有时,就是要最少的后者的因子凑出大于等于后者因子的最小次幂,处理完每一个因子后取因子需要的最大值,用它去更新答案。

注意m1=1时的特殊情况。

因为试管数目m=m1^m2,非常大,所以肯定不能用si来除,于是想到将m1分解,用数组cup存下m1分解后的质因数和对应的幂,将每个幂*m2即可表示m。
然后是n个si。一开始有点偷懒,写了一个过程来分解m1,分解si也直接调用这个过程,将si也分解成一个数组cup2,然后比较两个数组对应的质因数的幂。若cup的幂 mod cup2的幂=0 那么时间=cup的幂 div cup2的幂,否则,时间=cup的幂 div cup2的幂 +1,对于一个si中每个质因数的时间取最大,对于每个si的最大时间取最小。
但是过了8个数据,最后两组数据超时。仔细一想,对于每个si,并不需要将其全部分解,只需要拿si去整除cup的幂,用整除的次数k代替cup2的幂。这样避免了将si分解,可以节省非常大的时间开销,毕竟有些大的质因数需要找很长时间,n的值大了就超时。
另外,注意1的情况。
代码:
var cup:array[1..30000,1..2] of longint;
n,m1,m2,length,t,p,i,j,minest,max,k,si:longint;
f,flag:boolean;
begin
// assign(input,'cell.in'); assign(output,'cell.out');reset(input);rewrite(output);
readln(n);
readln(m1,m2);
fillchar(cup,sizeof(cup),0);
length:=1;
t:=m1;
for i:=2 to 2000000000 do
begin
if t=1 then break;
f:=false;
while t mod i=0 do
begin
f:=true;
inc(cup[length,2]);
t := t div i;
end;
if f then begin cup[length,1]:=i; inc(length); end;
end;
dec(length);
for i:=1 to length do
cup[i,2]:=cup[i,2]*m2;
minest:=2000000000;
for i := 1 to n do
begin
read(si);
if si=1 then continue;
flag:=true;
max:=0;
for j:=1 to length do
begin
k:=0;
while si mod cup[j,1]=0 do
begin
si := si div cup[j,1];
inc(k);
end;
if k=0 then begin flag:=false; break; end;
if cup[j,2] mod k = 0 then p:= cup[j,2] div k
else p:=cup[j,2] div k +1;
if p > max then max := p;
end;
if flag and (max<minest) then minest:=max;
end;
if minest=2000000000 then writeln('-1')
else writeln(minest);
// close(input); close(output);
end.

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com