Description

有n个正整数a[i]，设它们乘积为p，你可以给p乘上一个正整数q，使p*q刚好为正整数m的阶乘，求m的最小值。

 

Input

共两行。

第一行一个正整数n。

第二行n个正整数a[i]。

 

Output

共一行

一个正整数m。

 

Solutions

可以把p分解质因数，假设p=∏ai^bi（ai为质数），那么只要m！包含了每个ai^bi，m！就包含p。

所以对于每个ai^bi，分别求出满足条件的最小的m，取最大值即可。

怎么求m？

先看一个简单的问题：

27！里面有多少个3相乘？

27！=1*2*...*27

包含1个3的数有27/(3^1)=9个

包含2个3的数有27/(3^2)=3个

包含3个3的数有27/(3^3)=1个

总共：9+3+1=13个

所以27！里面有13个3相乘。

用这个方法就可以求得m！有多少个ai相乘，二分判断即可。

 

代码

1 var  2   n,m,nm,max:longint;  3   shi:array [0..10001] of longint;  4   a,v:array [0..100001] of longint;  5 procedure try1;  6 var  7   i,j:longint;  8   bo:boolean;  9 begin 10   fillchar(v,sizeof(v),0); 11   m:=0; 12   for i:=2 to 100000 do 13     begin 14       bo:=true; 15       for j:=2 to trunc(sqrt(i)) do 16         if i mod j=0 then 17           begin 18             bo:=false; 19             break; 20           end; 21       if bo then 22         begin 23           inc(m); 24           shi[m]:=i; v[i]:=1; 25         end; 26     end; 27 end; 28  29 procedure init; 30 var 31   i,j,x:longint; 32 begin 33   fillchar(a,sizeof(a),0); 34   readln(n); nm:=0; max:=0; 35   for i:=1 to n do 36     begin 37       read(x); 38       j:=1; 39       while x<>1 do 40         begin 41           if v[x]=1 then 42             begin 43               if x>max then max:=x; 44               inc(nm); inc(a[x]); 45               break; 46             end; 47           while x mod shi[j]=0 do 48             begin 49               inc(nm); 50               inc(a[shi[j]]); 51               x:=x div shi[j]; 52             end; 53           if (a[shi[j]]>0) and (shi[j]>max) then 54             max:=shi[j]; 55           inc(j); 56         end; 57     end; 58 end; 59  60 function fd(x:longint):boolean; 61 var 62   i:longint; 63   j,ans:int64; 64 begin 65   i:=1; 66   while (shi[i]<=max) and (i<=m) do 67     begin 68       j:=shi[i]; ans:=0; 69       while j
        
         =a[shi[i]] then break; 74         end; 75       if ans