5791. 【NOIP2008模拟】阶乘

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<x do
 70         begin
 71           ans:=ans+x div j;
 72           j:=j*shi[i];
 73           if ans>=a[shi[i]] then break;
 74         end;
 75       if ans<a[shi[i]] then exit(false);
 76       inc(i);
 77     end;
 78   exit(true);
 79 end;
 80 
 81 procedure main;
 82 var
 83   l,r,mid:longint;
 84 begin
 85   l:=max; r:=10000000;
 86   while l<=r do
 87     begin
 88       mid:=(l+r) div 2;
 89       if fd(mid) then r:=mid-1
 90                  else l:=mid+1;
 91     end;
 92   writeln(r+1);
 93 end;
 94 
 95 begin
 96   assign(input,'factorial.in');
 97   assign(output,'factorial.out');
 98   reset(input);
 99   rewrite(output);
100   try1;
101   init;
102   main;
103   close(input);
104   close(output);
105 end.