70284 - CSP-S第一轮同测模拟卷1阅读程序1
统计题目(材料题)
01 #include<iostream>
02 #include<vector>
03 using namespace std;
04 int solve1(int n) {
05 vector<int> pri;
06 vector<bool> np(n + 1, false);
07 vector<int> phi(n + 1, 0);
08 phi[1] = 1;
09 for (int i = 2; i <= n; i++) {
10 if (!np[i]) {
11 pri.push_back(i);
12 phi[i] = i - 1;
13 }
14 for (int p : pri) {
15 if (i * p > n) break;
16 np[i * p] = true;
17 if (i % p == 0) {
18 phi[i * p] = phi[i] * p;
19 break;
20 }
21 phi[i * p] = phi[i] * phi[p];
22 }
23 }
24 int ans = 0;
25 for (int v : phi) ans += v;
26 return ans;
27 }
28 int solve2(int n) {
29 int ans = n * (n - 1) / 2;
30 for (int i = 2; i <= n / 2; i++) {
31 ans -= (n / i) - 1;
32 }
33 return ans;
34 }
35 int main() {
36 int n;
37 cin >> n;
38 cout << solve1(n) << endl;
39 cout << solve2(n) << endl;
40 return 0;
41 }
假设输入的n是一个不超过10000的正整数，完成下面的判断题和单选题。
关注我们
