123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051 |
- #include <bits/stdc++.h>
-
- using namespace std;
- vector<int> phi;
-
- void genPhi(int max) {
- int minDiv[max];
- for (int i = 1; i < max; i++) {
- minDiv[i] = i;
- }
- for (int i = 2; i * i < max; i++) {
- if (minDiv[i] == i) {
- for (int j = i * i; j < max; j += i) {
- minDiv[j] = i;
- }
- }
- }
- phi[1] = 1;
- for (int i = 2; i < max; i++) {
- phi[i] = phi[i / minDiv[i]];
- if ((i / minDiv[i]) % minDiv[i] == 0) {
- phi[i] *= minDiv[i];
- } else {
- phi[i] *= minDiv[i] - 1;
- }
- }
- }
-
- const int MAXN = 1000001;
- long long g[MAXN];
- int f[MAXN];
-
- int main() {
- // ofstream cout("output.txt");
- phi.resize(MAXN);
- genPhi(MAXN);
- for (int i = 1; i <= MAXN; i += 2) {
- f[i] = phi[i] % (i + 1);
- }
- g[0] = 0;
- for (int i = 1; i <= MAXN; i++) {
- g[i] = g[i - 1] + f[i];
- }
- int T;
- cin >> T;
- for (int t = 1; t <= T; t++) {
- int n;
- cin >> n;
- cout << "Case " << t << ": " << g[n] << endl;
- }
- }
|