【JZOJ5791】阶乘【二分】【数论，数学】

题目大意：

题目链接：https://jzoj.net/senior/#main/show/5791
题目图片：
http://wx2.sinaimg.cn/mw690/0060lm7Tly1fvxbuy446bj30j608kglm.jpg
http://wx3.sinaimg.cn/mw690/0060lm7Tly1fvxbuy44q9j30j40bbt8r.jpg
给出$n$个数$a[1],a[2]...a[n]$，求$a[1]\times a[2]\times ...\times a[n]$是$m!$因数的最小的$m$。

---

思路：

首先，我们可以把这$n$个数分解质因数，并将每个质因数存在一个桶里。
那么我们设分解后有$k[1]$个$x[2]$，$k[2]$个$x[2]...k[m]个x[m]$，那么原本的$a[1]\times a[2]\times...\times a[n]$就变成了：
$x[1]^{k[1]}\times x[2]^{k[2]}\times...\times x[m]^{k[m]}$
其实也就是说，将m!分解质因数后一定含有k[1]个x[1]，k[2]个x[2]，一直到k[m]个x[m]。
我们知道，如果$m!$分解质因数后含有$x[1]^{k[1]}\times x[2]^{k[2]}\times...\times x[m]^{k[m]}$，那么$(m+1)！$就一定含有$x[1]^{k[1]}\times x[2]^{k[2]}\times...\times x[m]^{k[m]}$。
原因很简单。

证：
设$T=x[1]^{k[1]}\times x[2]^{k[2]}\times...\times x[m]^{k[m]}$，那么由于$m!$分解质因数后含有$T$,那么$m!$就可以写成$Tx$，其中$x$为正整数。
由于
$(m+1)!=m!\times (m+1)=Tx(m+1)$
所以$(m+1)！$就一定含有$x[1]^{k[1]}\times x[2]^{k[2]}\times...\times x[m]^{k[m]}$
证毕。

所以，也就是说，$m!$里含有的因式$(m+1)$一定含有，那么$(m+2)$也含有，$(m+3)$也含有。。。
所以，这个阶乘很明显是单调的。
那么就可以二分答案$q$。若$q！$含有$k[1]$个$x[1]$，$k[2]$个$x[2]...k[m]$个$x[m]$，那么$q!$就是合法的解，由此又可以得到大于$q$的数的阶乘也是合法的解。所以最小的答案就在$[1,q]$中。
否则就在$[q+1,MAXN]$中。
$MAXN$的话设大一点就好了。反正二分又不会很多次。
时间复杂度：$O(n\sqrt{n}+nlogn)$

---

代码：

#include <cstdio>
#include <cmath>
#define ll long long
#define N 5000100
using namespace std;

int n,m,l,r,mid,num[N];

bool check(int x)
{
	int sum;
	ll y;
	for (int i=2;i<=N;i++)
	{
		if (!num[i]) continue;
		sum=0;
		y=(ll)i;
		while (y<=(ll)x)
		{
			sum=sum+(x/(int)y);  //记录有多少个i
			if (sum>num[i]) break;
			y*=i;
		}
		if (sum<num[i]) return false;  //不够
	}
	return true;
}

int main()
{
	scanf("%d",&n);
	int x;
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		for (int j=2;j*j<=x;j++)
		 while (!(x%j))
		 {
		 	num[j]++;  //分解质因数
		 	x/=j;
		 }
		if (x>1) num[x]++;
	}
	l=1;
	r=N-1;
	while (l<=r)
	{
		mid=(l+r)/2;
		if (check(mid)) r=mid-1;
		 else l=mid+1;
	}
	printf("%d\n",r+1);
	return 0;
}