题目(材料题)
|
|
01 #include <iostream>
02 #include <cmath>
03 #include <vector>
04 #include <algorithm>
05 using namespace std;
06
07 long long solve1(int n) {
08 vector<bool> p(n + 1, true);
09 vector<long long> f(n + 1, 0), g(n + 1, 0);
10 f[1] = 1;
11 for (int i = 2; i * i <= n; i++) {
12 if (p[i]) {
13 vector<int> d;
14 for (int k = i; k <= n; k *= i) d.push_back(k);
15 reverse(d.begin(), d.end());
16 for (int k : d) {
17 for (int j = k; j <= n; j += k) {
18 if (p[j]) {
19 p[j] = false;
20 f[j] = i;
21 g[j] = k;
22 }
23 }
24 }
25 }
26 }
27 for (int i = sqrt(n) + 1; i <= n; i++) {
28 if (p[i]) {
29 f[i] = i;
30 g[i] = i;
31 }
32 }
33 long long sum = 1;
34 for (int i = 2; i <= n; i++) {
35 f[i] = f[i / g[i]] * (g[i] * f[i] - 1) / (f[i] - 1);
36 sum += f[i];
37 }
38 return sum;
39 }
40
41 long long solve2(int n) {
42 long long sum = 0;
43 for (int i = 1; i <= n; i++) {
44 sum += i * (n / i);
45 }
46 return sum;
47 }
48
49 int main() {
50 int n;
51 cin >> n;
52 cout << solve1(n) << endl;
53 cout << solve2(n) << endl;
54 return 0;
55 }
|
假设输入的 n 是不超过 1000000 的自然数，完成下面的判断题和单选题:
||
关注我们
