QQ扫一扫联系
#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;
}假设输入的 n 是不超过 1000000 的自然数，完成下面的判断题和单选题:
将第 15 行删去，输出不变。（）
当输入为 10 时，输出的第一行大于第二行。（）
当输入为 1000 时，输出的第一行与第二行相等。（）
solve1(n) 的时间复杂度为（）。
O(nlog2n)
O(n)
O(nlogn)
O(nloglogn)
solve2(n) 的时间复杂度为（）。
O(n2)
O(n)
O(nlogn)
O(nn)
当输入为 5 时，输出的第二行为（）。
20
21
22
23
