「CH3101」阶乘分解

题意：给定整数 $N(1\leq N\leq 10^6)$，把 $N!$ 分解质因数。

如果将 $1\sim N$ 分别分解质因数在合并，很明显不可行。

显然，$N!$ 的每个质因子都在 $N$ 之内，我们可以先把 $N$ 之内的质数先筛出来，就完成一半了。

然后就是难点求质数的幂了，设每个质数为 $p$，考虑 $N!$ 内包含多少 $p$。

我们可以运用小学奥数方法，包含一个质因子 $p$ 的在 $N$ 之内有 $\lfloor\frac{N}{p}\rfloor$ 个，包含两个质因子 $p^2$ 的在 $N$ 之内有 $\lfloor\frac{N}{p^2}\rfloor$ 个，以此类推，则 $N!$ 内中质因子 $p$ 的个数为：

$$\lfloor\frac{N}{p}\rfloor+\lfloor\frac{N}{p^2}\rfloor+\lfloor\frac{N}{p^3}\rfloor+···+\lfloor\frac{N}{p^{\lfloor log_p N\rfloor}}\rfloor=\sum_{p^k\leq N}\lfloor\frac{N}{p^k}\rfloor$$

时间复杂度为 $O(N\log N)$。

code:

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,c[1010101],p[1010101],vis[1010101],cnt;
int main()
{
	scanf("%d",&n);
	for(int i=2;i<=n;i++)
	{
		if(vis[i]==0)
		{
			vis[i]=i;
			p[++cnt]=i;
		}
		for(int j=1;j<=cnt;j++)
		{
			if(p[j]>vis[i]||p[j]*i>n)
				break;
			vis[i*p[j]]=p[j];
		}
	}
	for(int i=1;i<=cnt;i++)
	{
		int x=p[i];
		for(int j=n;j;j/=x)
			c[i]+=j/x;
		printf("%d %d\n",p[i],c[i]);
	}
    return 0;
}