test/aoj/2286.test.cpp

View this file on GitHub
Last update: 2022-12-30 14:22:43+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2286

Depends on

src/math/euler_phi_table.hpp

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2286"

#include <bits/stdc++.h>
using namespace std;

#include "../../src/math/euler_phi_table.hpp"

int main() {
  vector<int> table = euler_phi_table(1000000);
  vector<long long> sum(1000001, 0);
  for (int i = 1; i <= 1000000; i++) {
    sum[i] = sum[i - 1] + table[i];
  }

  int t;
  cin >> t;
  for (int i = 0; i < t; i++) {
    int n;
    cin >> n;
    cout << sum[n] + 1 << endl;
  }
  return 0;
}

#line 1 "test/aoj/2286.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2286"

#include <bits/stdc++.h>
using namespace std;

#line 2 "src/math/euler_phi_table.hpp"

#line 4 "src/math/euler_phi_table.hpp"
using namespace std;

template <typename T = int> vector<T> euler_phi_table(T n) {
  vector<T> res(n + 1);
  for (T i = 0; i <= n; ++i) {
    res[i] = i;
  }
  for (T i = 2; i <= n; ++i) {
    if (res[i] == i) {
      for (T j = i; j <= n; j += i) {
        res[j] -= res[j] / i;
      }
    }
  }
  return res;
}
#line 7 "test/aoj/2286.test.cpp"

int main() {
  vector<int> table = euler_phi_table(1000000);
  vector<long long> sum(1000001, 0);
  for (int i = 1; i <= 1000000; i++) {
    sum[i] = sum[i - 1] + table[i];
  }

  int t;
  cin >> t;
  for (int i = 0; i < t; i++) {
    int n;
    cin >> n;
    cout << sum[n] + 1 << endl;
  }
  return 0;
}