Simonenoip2009的
的有关信息介绍如下：
Problem 3: cell 细胞分裂
【分析】
仔细读题后可以发现，本题的实质就是求 中t的最小值.这样一来，我们可以直接使用高精度算法来枚举t的最小值.但高精度算法却不能处理任何细胞都不满足要求的情况.故而，我们需要进行简单的数学分析.
首先分析样例：
样例1
样例2
2
3
1
1
列成表格后可以得到：
，
列成表格后可以得到：
2
3
5
3
1
1
1
1
2
1
通过观察得知，如果i细胞可以满足情况时，那么 有的质因数， 也一定有.反之，若 有的质因数，没有，则i细胞不能满足情况.而 的充要条件就是 中质因数的次数大于等于 中相同的质因数的次数.至此，题意分析完毕.
接下来，我简单的说一下算法的实现过程：
（1） 构造一个1..30000的质数表，来分解质因数.
（2） 注意 的特殊情况，此时任何 都能整除 ，故而直接输出0.
（3） 分解 ，建立一个m数组储存分解结果.
（4） 分解 ,然后递增t，直到 .这里有个优化，其实分解 时只需处理 中有的质因数，同样，枚举t的时候也只需处理 中有的质因数.此外，还需要设置一个变量处理 中的质因数>30000的情况，一种较为简单的方法是对比每次 的值，连续两次相等则退出.
（5） 输出最终结果.
【程序】
type
prime=array[1..3250] of word;
var
n,m1,m2,t,min,time,last,i,j:longint;
//t:30000以内的质数个数
//min:最短时间
//last:监视当前s[i]值，防止死循环
si:array[1..10000] of prime; //si[i]的质因数个数
s:array [1..10000] of longint;
p:array [1..3250] of 1..30000;//30000以内的质数表
m:prime;//m1^m2的质因数个数
flag:boolean;
function ok(x:integer):boolean;//判断s[x]与m1^m2是否含有相同质因数
begin
ok:=true;
for j:=1 to t do
if (m[j]<>0) and (si[x][j]=0) then exit(false);
end;
function ok(x,y:integer):boolean;//判断s[x]^y是否整除m1^m2
begin
ok:=true;
for j:=1 to t do
if (m[j]<>0) and (si[x][j]*y
end;
begin
fillchar(m,sizeof(m),0);
fillchar(si,sizeof(si),0);
readln(n);readln(m1,m2);
for i:=1 to n do read(s[i]);
p:=2;p:=3;t:=2;//用试除法构造30000以内质数表
for i:=4 to 30000 do
begin
flag:=true;
for j:=2 to trunc(sqrt(i))+1 do
if i mod j = 0 then
begin flag:=false;break;end;
if flag then
begin
inc(t);
p[t]:=i;
end;
end;
if m1=1 then //处理m1为1的特殊情况
begin
writeln(0);
halt;
end;
while m1<>1 do //分解m1^m2
for i:=1 to t do
if m1 mod p[i] = 0 then
begin
inc(m[i]);
m1:=m1 div p[i];
end;
for i:=1 to t do m[i]:=m[i]*m2;
flag:=false;min:=65535;
for i:=1 to n do
begin
time:=1;last:=0;
if s[i]=1 then continue;
while s[i]<>1 do //分解si[i]
begin
for j:=1 to t do
if (m[j] <> 0) and (s[i] mod p[j] = 0) then
begin
inc (si[i][j]);
s[i]:=s[i] div p[j];
end;
if last=s[i] then break;
last:=s[i];
end;
if ok(i) then //判断是否可以整除
begin
flag:=true;
while not ok(i,time) do inc(time);//递增time，直到整除为止
if time
end;
end;
if flag then writeln(min) else writeln(-1);
end.
