比赛 EYOI暨SBOI暑假快乐赛6th 评测结果 AAAAATTTTT
题目名称 秒速五厘米 最终得分 50
用户昵称 lavey 运行时间 5.899 s
代码语言 C++ 内存使用 5.08 MiB
提交时间 2022-06-30 11:29:23
显示代码纯文本
#include <bits/stdc++.h>

using i64 = long long;

const int MOD = 1e9+7, N = 2e5+10;
int n;
int v[N], prime[N];
std::set<int> primes;
std::map<int, int> fact;

int pow(int x, int power) {
    int ret = 1;
    for (; power; power >>= 1, x *= x) 
        if (power & 1) ret *= x;
    return ret;
}

void divide(int n) {
    memset(v, 0, sizeof v);
    int m = 0;
    for (int i = 2; i <= n; ++ i) {
        if (v[i] == 0) v[i] = i, prime[++ m] = i;
        for (int j = 1; j <= m; ++ j) {
            if (prime[j] > v[i] || prime[j] > n / i) break;
            v[i * prime[j]] = prime[j];
        }
    }
    for (int i = 1; i <= m; ++ i) primes.insert(prime[i]);
}

int main() {
    freopen("sakuras.in", "r", stdin); 
    freopen("sakuras.out", "w", stdout);
    std::cin >> n;
    for (int i = 1; i <= n; ++ i) divide(i);
    for (auto i : primes) {
        int power = 1, res = 0, now;
        while (now = n / pow(i, power)) ++ power, res += now;
        fact[i] = res;
    }
    i64 ans = 1;
    for (auto [x, y] : fact) ans = ans % MOD * (2 * y % MOD + 1 % MOD) % MOD;
    std::cout << ans << '\n';
    return 0;
}