用户输出
67326849456
系统信息
Exited with return code 0
编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
---|---|---|---|---|---|---|---|---|
#20478 | #1072. zzy与飞行棋 | Accepted | 100 | 82 ms | 2184 K | C++ 17 / 1.4 K | q3540555 | 2019-07-22 15:28:46 |
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define spause() system("pause")
using namespace std;
typedef long long llong;
typedef unsigned long long ullong;
typedef pair<int, int> prdd;
typedef map<int, int> mpdd;
const int dinf = 0x7fffffff;
const llong llinf = 0x7fffffffffffffff;
const int p = 998244353;
llong starttime;
int phi[525000];
vector<int> ps;
int n;
llong ans = 0;
void Euler(int rge) {
phi[1] = 1;
for (int i = 2; i <= rge; i++) {
if (phi[i] == 0) {
phi[i] = i - 1;
ps.push_back(i);
}
for (int j = 0; j < ps.size() && ps.at(j) <= rge / i; j++) {
if (i % ps.at(j) == 0) {
phi[i * ps.at(j)] = phi[i] * ps.at(j);
break;
} else
phi[i * ps.at(j)] = phi[i] * (ps.at(j) - 1);
}
}
}
// I. phi(p) = p - 1.
// II. if : i mod p = 0 -> phi(i * p) = phi(i) * p.
// III. if : i mod p �� 0 -> phi(i * p) = phi(i) * (p-1).
inline llong ngmod(llong a, llong p) { return ((a % p) + p) % p; }
int main() {
scanf("%d", &n);
Euler(n);
for (int i = 1; i <= n; i++) ans += phi[i];
ans *= 6;
printf("%lld", ans);
spause();
return 0;
}