题目

题目描述

给出 \(N\) ,求 \(1\) 到 \(N\) 个数中选出任意个数相乘能组成的最大平方数,由
于此数可能很大,你只需要输出此数除 \(100000007\) 的余数即可。

样例输入

样例输出

样例解释

\(2\times 3 \times 4\times 6=144\)

数据下载

由于各大oj可能没有，故在此提供测试数据

题解

题目就是这么简单，然而考试并没有想到\(QAQ\)
因为是任意个数相乘，我们可以将\(N!\)进行质因数分解
然后因为\(A^2\times B^2=(A\times B)^2\)
我们就可以把所有的2的整数倍次方全部乘入答案里，就是最大的平方数。

而普通的方法分解\(N!\)需要\(O(N\sqrt{N})\)的时间复杂度，我们可以考虑一种新方法。

显然，\(N!\)的每个质因子都不会超过\(N\)，我们可以先筛选出\(1-N\)的每个质数\(p\)，然后考虑阶乘中一共包含多少个质因子\(p\)

\(N!\)中质因子\(p\)的个数就等于\(1-N\)每个数包含的质因子\(p\)的个数之和。在\(1-N\)中，\(p\)的倍数，即至少包含1个质因子\(p\)的显然有\(\lfloor N/p \rfloor\)个。而\(p^2\)的倍数，即至少包含2个质因子\(p\)的有\(\lfloor N/p^2 \rfloor\)个。不过其中的一个质因子已经在\(\lfloor N/p \rfloor\)中统计过，所以只需要再统计第2个质因子，即累加上\(\lfloor N/p^2 \rfloor\)，而不是\(2\times \lfloor N/p^2 \rfloor\)

综上所述，\(N!\)中质因子\(p\)的个数为：

\left\lfloor \frac{N}{P} \right\rfloor+\left\lfloor \frac{N}{P^2} \right\rfloor+\left\lfloor \frac{N}{P^3} \right\rfloor+\dots+\left\lfloor \frac{N}{P^{\lfloor log_p N \rfloor}} \right\rfloor=\sum_{p^k\le N}\left\lfloor \frac{N}{P^k} \right\rfloor

上面的计算只需要\(O(logN)\)的时间
整个过程只需要\(O(NlogN)\)的时间

代码