Участник:Nik7/GCD Extreme

Материал из DISCOPAL
Перейти к: навигация, поиск

«GCD Extreme»

// C++14 (gcc 8.3)
#include <cstdint>
#include <iostream>
#include <vector>
 
constexpr auto N_MAX = 1'000'001lu;
 
int main() {
  auto phi = std::vector<std::uint64_t>(N_MAX);
  auto G = std::vector<std::uint64_t>(N_MAX);
  for (auto i = 2lu; i < N_MAX; ++i) {
    if (phi[i] == 0) {
      phi[i] = i - 1;
      for (auto j = i + i; j < N_MAX; j += i) {
        if (phi[j] == 0) {
          phi[j] = j;
        }
        phi[j] = phi[j] - phi[j] / i;
      }
    }
  }
  for (auto i = 1; i < N_MAX; ++i) {
    for (auto j = i; j < N_MAX; j += i) {
      G[j] = G[j] + (i * phi[j / i]);
    }
  }
  for (auto i = 1; i < N_MAX; ++i) {
    G[i] = G[i] + G[i - 1];
  }
  std::int32_t n;
  std::cin >> n;
  while (n != 0) {
    std::cout << G[n] << std::endl;
    std::cin >> n;
  }
  return 0;
}