1 条题解

  • 0
    @ 2025-3-27 17:15:03
    #include <bits/stdc++.h>
    using namespace std;
    const int MOD = 1000000007;
    const int maxn = 1000001;
    int n, vis[maxn], prime[maxn], tot, bt[maxn] = {0}; // 初始化 bt
    long long ans = 1;
    
    void euler() {
        vis[1] = 1;
        for (int i = 2; i <= n; ++i) {
            if (!vis[i]) prime[++tot] = i;
            for (int j = 1; j <= tot; ++j) {
                if (prime[j] * i > n) break;
                vis[prime[j] * i] = 1;
                if (i % prime[j] == 0) break; // 关键修复
            }
        }
    }
    
    int main() {
        scanf("%d", &n);
        if (n >= maxn) {
            printf("Input too large!\n");
            return 0;
        }
        euler();
        for (int i = 2; i <= n; ++i) {
            int x = i;
            for (int j = 1; j <= tot; ++j) {
                if (prime[j] > x) break;
                if (!vis[x]) {
                    bt[x] += 2;
                    break;
                }
                if (x % prime[j] == 0) {
                    int res = 0;
                    while (x % prime[j] == 0) {
                        x /= prime[j];
                        res++;
                    }
                    bt[prime[j]] += res * 2;
                }
            }
        }
        for (int i = 1; i < maxn; ++i) { // 修复越界
            if (bt[i]) ans = (ans * (bt[i] + 1)) % MOD;
        }
        printf("%lld", ans);
        return 0;
    }
    
    • 1

    信息

    ID
    1080
    时间
    1000ms
    内存
    512MiB
    难度
    10
    标签
    递交数
    6
    已通过
    1
    上传者