题目描述

给定一个正整数 $n$，求能被 $[1, n]$ 内所有数整除的最小数字（即最小公倍数 $\text{LCM}(1,2,\dots,n)$），并对 $100000007$ 取模。

输入格式
一行一个整数 $n$。

输出格式
一行一个整数，表示答案。

样例
输入：

10

输出：

2520

数据范围
$n \leq 10^8$

算法思路

1. 问题分析

我们需要计算： $\text{LCM}(1, 2, \dots, n) \bmod 100000007$ 根据数论知识，最小公倍数可以表示为所有质数幂的乘积： $ \text{LCM}(1,2,\dots,n) = \prod_{p \ \text{prime}} p^{e_p} $ 其中 $e_p$ 是满足 $p^{e_p} \le n$ 的最大整数。

2. 关键观察

对于每个质数 $p$，我们需要找到最大的 $k$ 使得 $p^k \le n$，然后将 $p^k$ 乘到答案中。

原理

• $\text{LCM}$ 必须包含足够的质因子幂次，以覆盖 $1$ 到 $n$ 中所有数的质因数分解
• 对于质数 $p$，$n$ 以内 $p$ 的最高次幂就是 $p^{\lfloor \log_p n \rfloor}$
• 这样才能确保所有 $p$ 的倍数、平方倍数等都被覆盖

3. 算法步骤

1. 使用线性筛法找出所有不超过 $n$ 的质数
2. 对每个质数 $p$，计算 $p^k \le n$ 的最大 $k$
3. 将所有这样的 $p^k$ 相乘，并对 $100000007$ 取模
4. 输出结果

4. 复杂度分析

• 时间复杂度：$O(n)$
  • 线性筛法时间复杂度为 $O(n)$
  • 每个质数求幂次的时间可以忽略
• 空间复杂度：$O(n)$
  • 需要数组标记合数和存储质数

对于 $n \leq 10^8$，该算法在时间和空间上都是可行的。

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100000003
#define MX 10000
#define LL long long
#define p 100000007
using namespace std;

bool pd[N];
int n, prime[6000000];

int main() {
    scanf("%d", &n);
    LL ans = 1;

    for (int i = 2; i <= n; i++) {
        if (!pd[i]) {  // i是质数
            prime[++prime[0]] = i;
            LL t = i;

            // 找到不超过n的最大p的幂
            while (t * (LL)i <= n)
                t *= i;

            ans = ans * t % p;
        }

        for (int j = 1; j <= prime[0]; j++) {
            int k = i * prime[j];

            if (k > n)
                break;

            pd[k] = 1;  // 标记合数

            if (i % prime[j] == 0)
                break;  // 保证每个合数被最小质因子筛掉
        }
    }

    printf("%lld\n", ans);
    return 0;
}

样例验证

以 $n = 10$ 为例：

• 质数 $2$：$2^3 = 8 \le 10$
• 质数 $3$：$3^2 = 9 \le 10$
• 质数 $5$：$5^1 = 5 \le 10$
• 质数 $7$：$7^1 = 7 \le 10$

乘积：$8 \times 9 \times 5 \times 7 = 2520$，与样例输出一致。

总结

本题的关键在于：

1. 理解 $\text{LCM}(1,\dots,n)$ 的质因数分解形式
2. 使用线性筛法高效枚举所有质数
3. 对每个质数取不超过 $n$ 的最高次幂
4. 将所有质数幂相乘得到最终结果

该解法充分利用了数论性质，在线性时间内解决了问题，能够高效处理 $n = 10^8$ 的大数据范围。