最小公倍数

coding>C++
878 词

题目描述

为什么1小时有60分钟，而不是100分钟呢？这是历史上的习惯导致。

但也并非纯粹的偶然：60是个优秀的数字，它的因子比较多。

事实上，它是1至6的每个数字的倍数。即$1,2,3,4,5,6$都是可以除尽$60$。

我们希望寻找到能除尽1至n的的每个数字的最小整数m。

如果这个数很大，请输出对$1000000007$取模后的结果。

输入

只有一个数n(1<=n<=10000).

输出

输出m对1000000007取模的结果。

样例输入

1
4

样例输出

1
12

提示

数论

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <map>
using namespace std;
typedef long long LL;
LL MOD = 1000000007L;
map<int, int> M;
inline bool prime(int n) {
    if (n == 2) return true;
    if (n < 2  n % 2 == 0) return false;
    for (int i = 3; i <= n / i; i += 2)
        if (n % i == 0) return false;
    return true;
}
inline int log(int n, int base) {
    if (n < base) return 0;
    return 1 + log(n / base, base);
}
int main() {
    LL ans = 1LL;
    int n;
    cin >> n;
    M[2] = log(n, 2);
    for (int i = 3; i <= n; i += 2) {

        if (prime(i)) M[i] = log(n, i);
    }
    for (auto m : M) {

        for (int i = 1; i <= m.second; i++) ans = (ans * m.first) % MOD;
    }
    cout << ans << endl;
    return 0;
}