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

using i64 = long long;

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

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

void divide(i64 n) {
    memset(v, 0, sizeof v);
    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];
        }
    }
}

int main() {
    freopen("sakuras.in", "r", stdin); 
    freopen("sakuras.out", "w", stdout);
    std::cin >> n;
    divide(n);
    for (int i = 1; i <= m; ++ i) {
        i64 power = 1, res = 0, now;
        while (now = n / pow(prime[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;
}