简要题意：
求能被 (1) ~ (n) 整除的最小的数。
真是一道水题
显然求 (operatorname{lcm}{1,2, cdots n})，（(operatorname{lcm}) 表示 最小公倍数）
对于 (n leq 10^8) 这种数据范围，显然，如果我们枚举最小公倍数（？？），将每个数分解质因数然后合并结果，或者对每两个数取最小公倍数的话，一来不能保证最优答案，而来也不能在 (1s) 内解决问题。
所以，考虑另一种基于分解质因数的方法。
首先把 (1) ~ (n) 筛素数记录为 (p_1 , p_2 cdots p_k) ，那么所有数都可以写成：
嗯，此时，因为质因数分解重新定义了最小公倍数的概念，所以，我们 对每个质因数求出其最大幂次即可。
那么这个怎么求？其实就是 (leq n) 的 (p_i) 的幂次，这些数相乘就是答案。
对于最大幂次的求法，累乘直到 再乘一次就超过 (n) 为止。其中 当前幂次再乘一次 的这个结果要注意开 ( ext{long long})，因为可能爆 ( ext{int}).
对于筛素数的过程，我们用线性筛素数（欧拉筛）。
题解区里很多人都说要卡常。但是我的程序没这个必要，因为我们算法已经最优了，提交结果 (1) 次 (2.75s ext{AC}) 不算优，但是没有常熟优化的情况下已经不错了。
时间复杂度：(O(n)).（程序后会详细说明）
实际得分：(100pts).
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=1e8+7;
const int N=1e8+1;
const int SN=1e7+1;
inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
bool h[N]; int cnt=0;
int n,prime[SN];
ll ans=1;
inline void Euler() {
for(int i=2;i<=n;i++) {
if(!h[i]) prime[++cnt]=i;
for(int j=1;j<=cnt && i*prime[j]<=n;j++) {
h[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
} //欧拉筛模板
inline ll dg(int x) {
int y=x;
while((ll)y*x<=n) x*=y;
return x;
} //计算质数 x <= n 的最大幂次
int main(){
n=read(); Euler();
for(int i=1;i<=cnt;i++) {
ll x=dg(prime[i]);
ans=(ans*x)%MOD; //累乘记录答案
} printf("%lld
",ans);
return 0;
}
注：
关于 (O(n)) 的说明：(n) 是数据范围，而欧拉筛是线性的。所以我们只要计算，累乘的时间是多少了。用 (k) 表示 (leq n) 的素数个数，(S) 为素数之和。
那么我们要知道 (k) 和 (S) 大概是多少，所以写了一个测试程序。（因为非该题 ( ext{std})，所以请右转访问）
测试结果：
( ext{ans}) 这么大，大概是多少？是 (2 imes 10^{14}) 左右，我们保留 最高位下的一位小数 可得：
上述 (k leq 5.7 imes 10^6)，(S leq 2 imes 10^{14}).
嗯，时间复杂度大概是多少？应该是 以所有素数为底的 (n) 的对数之和，我们只需要把本题的程序改一改，用
测试结果： (5762860).
所以这完全是个大常数而已，和 (O(n)) 差不多，你会发现 大多数以素数为底的对数均为 (1)，而最大的也就是 (log_2 10^8 = 30)，无足为奇。
因此经过计算，抛开大常数而言，时间复杂度为 (O(n)).
内存复杂度本题需要注意，(10^8) 个 ( ext{bool}) 占 (10^8 B)，(10^7) 个 ( ext{int}) 占 (4 imes 10^7 B)，经过计算，只需要
似乎超了？但是，(10^7) 个 ( ext{int}) 只会用到 (6 imes 10^6) 个（剩下开的不用，就不会被计算），则为：
而实际提交为约 (120.30MB)，加上运行内存，大概符合估算，可以说是正好卡过了内存限制。