2.
假设输入的 nn 是不超过 10000001000000 的自然数，完成下面的判断题和单选题:
- #include <iostream>
- #include <cmath>
- #include <vector>
- #include <algorithm>
- using namespace std;
- long long solve1(int n) {
- vector<bool> p(n + 1, true);
- vector<long long> f(n + 1, 0), g(n + 1, 0);
- f[1] = 1;
- for (int i = 2; i * i <= n; i++) {
- if (p[i]) {
- vector<int> d;
- for (int k = i; k <= n; k *= i)
- d.push_back(k);
- reverse(d.begin(), d.end());
- for (int k : d) {
- for (int j = k; j <= n; j += k) {
- if (p[j]) {
- p[j] = false;
- f[j] = i;
- g[j] = k;
- }
- }
- }
- }
- }
- for (int i = sqrt(n) + 1; i <= n; i++) {
- if (p[i]) {
- f[i] = i;
- g[i] = i;
- }
- }
- long long sum = 1;
- for (int i = 2; i <= n; i++) {
- f[i] = f[i / g[i]] * (g[i] * f[i] - 1) / (f[i] - 1);
- sum += f[i];
- }
- return sum;
- }
- long long solve2(int n) {
- long long sum = 0;
- for (int i = 1; i <= n; i++) {
- sum += i * (n / i);
- }
- return sum;
- }
- int main() {
- int n;
- cin >> n;
- cout << solve1(n) << endl;
- cout << solve2(n) << endl;
- return 0;
- }
判断题
1将第 1515 行删去，输出不变。（）
2当输入为 10 时，输出的第一行大于第二行。（）
3（2 分） 当输入为 1000 时，输出的第一行与第二行相等。（）
单选题
4solve1(n) 的时间复杂度为（）。
5solve2(n) 的时间复杂度为（）。
6当输入为 5 时，输出的第二行为（）。
1.
A. 正确
B. 错误
2.
A. 正确
B. 错误
3.
A. 正确
B. 错误
4.
A. O(n \log^2 n)O(nlog2n)
B. O(n)O(n)
C. O(n \log n)O(nlogn)
D. O(n \log\log n)O(nloglogn)
5.
A. O(n^2)O(n2)
B. O(n)O(n)
C. O(n \log n)O(nlogn)
D. O(n \sqrt n)O(nn)
6.
A. 20
B. 21
C. 22
D. 23
