1 条题解
-
0
#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
- 上传者