1724: 结束了(hard version)

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：0 解决：18

题目描述

小m的大学生涯很快就到了毕业的时候，此时，他感叹大学生涯过的好快啊，然后自己又留下来学一年实际上挂科延毕了

他想起来，那一年，自己向一个女孩子表白，那个女孩子回给自己了一段程序；同一年，又向一个女孩子表白，那个女孩子给了自己一道题。想到这，他恍然大悟，原来女生都是喜欢做题的啊，这次他准备万全，准备最后一次告白。

“嘿，小s，你知道lcm嘛?”

“?”

“lcm就是最小公倍数啦~”

“?”

接着小m又说了很多很多，但是小s对那些并没有兴趣，小s只是想着怎么才能免费喝杯奶茶。不过小m丝毫不慌，拿出自己的mpad2021 pro max plus plus 上面写着

“我延毕了，因为我想着这样就能和你一起毕业了。”

小s在等着下一句话。

“为了以防你也延毕，让我们一起来解答这个问题吧。”

…

“草原上有一个兔子王国，里面有n只兔子公民，编号为1到n，公民在每年劳作之后要向国王缴纳税款，每只兔子缴纳的税款和自己的编号相同。但是国王的收税库被施了魔法，只能接受能把自己的容量整除的数量。现在国王想尽可能多的收税，但是不想提供过多的容量，请你给出一个最小的容量数吧~”

小s不关注题是什么，小s只想喝奶茶。现在小s把题目给你了，请你把答案告诉她吧~

输入

一个整数n。(1<= n <= 1e8)

输出

一个整数表示最小的容量数。由于答案可能过大，请把答案对1e9+7取模。

样例输入 复制 

3

样例输出 复制 

6

提示

小m为了不让小s延毕，热心的另外告诉了一组样例：

输入样例 

20

输出样例 

232792560

另外还担心小s可能不会线性时间筛素数，直接把线性筛素数的代码也给你了，他真的不想让小s延毕啊延毕了自己又得再延一年才能一起毕业了。 

//C++ 使用C++的话推荐手动开启O2优化 
#pragma GCC optimize("O2")
const int max_n = 1e8 + 100;
int primes[6000000], id = 0;
bool used[max_n];
//primes里面存的素数，used[i] == 0 代表i是素数 id代表素数的数量 运行完init() 函数之后 直接用这几个数组然后提交的时候选择 C++ 就行了
void init(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!used[i])
            primes[id++] = i;
        for (int j = 0; j < id && i * primes[j] <= n; j++)
        {
            used[i * primes[j]] = true;
            if (i % primes[j] == 0)
                break;
        }
    }
}



来源/分类