用户输出
67326849456
系统信息
Exited with return code 0
编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
---|---|---|---|---|---|---|---|---|
#21410 | #1072. zzy与飞行棋 | Accepted | 100 | 76 ms | 4132 K | C++ 17 / 849 B | 自动化82-郭筠陶 | 2020-02-06 17:31:37 |
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int max_ = 4e5 + 10;
vector<ull> phi(max_, 0);
vector<ull> primes;
void getPhi();
int main() {
int n;
cin >> n;
getPhi();
ull ans = 0;
for (int i = 1; i <= n; ++i) {
ans += phi.at(i);
}
cout << ans * 6;
return 0;
}
void getPhi() {
phi.at(1) = 1;
for (int i = 2; i < max_; i++) {
if (phi.at(i) == 0) {
primes.push_back(i);
phi.at(i) = i - 1;
}
for (int j = 0; j < primes.size() && primes.at(j) * i < max_; ++j) {
int prime = primes.at(j);
if (i % prime == 0) {
phi.at(i * prime) = phi.at(i) * prime;
break;
} else {
phi.at(i * prime) = phi.at(i) * (prime - 1);
}
}
}
}