传送门：https://loj.ac/problem/6165
这题“一道水题”，一道非常难的数学题。（主要是我不会线性筛）
先来讲一下线性筛（欧拉筛法）：
我们从2一直找到\(n\)，如果这个数没有被标记为非质数，就把它放进一个记录目前找到的所有质数的数组\(prime\)里面，并且用\(pri\)这个数记录下当前有多少个质数。
然后我们把从\(prime[1]\)到\(prime[pri]\)和当前的数\(i\)的乘积标记为非质数，如果乘积超过\(n\)就结束循环。
慢着，这不是和普通筛法一样？关键的来了！！！
这是线性筛中非常关键的一行代码：

正是它，使得这种筛法变为线性的。
因为如果\(i\)是\(prime[j]\)的倍数，那么之前在删\(prime[j]\)和别的数的乘积的时候肯定已经把\(i\)的倍数删掉了。如果不好理解，可以自己模拟一下。
这样，每个合数都会被删掉，并且不会被重复删掉。这使得它的复杂度成为线性的了。
普通筛法——埃拉托斯特尼筛法的时间复杂度为\(O(n\ log\ log\ n)\)，空间复杂度为\(O(n)\)。如果数据中\(n\)达到了\(10^8\)（比如现在讲的这题），那么就会超时。
这种筛法——欧拉筛法的时间复杂的为\(O(n)\)。
讲完线性筛，再来讲讲这题的做法。
这题是要求\([1,n]\)中所有数的最小公倍数模\(10^8+7\)的值，其实也就是求每一个数分解质因数后，把所有质数的次数取最高次然后乘起来。例如题目样例，\(1\sim 10\)中，2的最高次是3（\(8=2^3\)），3的最高次是2（\(9=3^2\)），5的最高次是1，7的最高次也是1，那么最终的答案为\(2^3\times 3^2\times 5\times 7=2520\)。
我们在筛每一个质数\(i\)的之前，就可以先计算出它的最高次应该是多少（即使得\(i^t\leq n\)的最大的\(t\)），然后把它乘进\(ans\)中并对\(10^8+7\)取模即可（初始化\(ans=1\)）。
这样做时间复杂度当然是\(O(n)\)的，但是由于有常数，并且时间限制只有\(1s\)，我们还需要进行常数上的优化。由于空间限制只有\(128MB\)，我们一定要注意空间问题。（我也不知道我是怎么把它优化到时空限制都符合要求的，反正我的原则是：能不开long long就不开long long，能不把变量开在循环里面就不把变量开在循环里面。再加上可能LOJ评测机的速度比较可观，就愉快地AC啦~）其实我优化了好久的QAQ。。。
AC代码：