math/alternative-totient-table.hpp

• View this file on GitHub
• Last update: 2023-07-08 14:12:19+09:00
• Include: #include "math/alternative-totient-table.hpp"

Depends on

• math/base.hpp
• math/count-factor.hpp

Code

#pragma once

#include "./base.hpp"
#include "./count-factor.hpp"

#include <vector>

namespace matumoto {
  // Θ(NloglogN)
  vector<int> alternative_totient_table(int N) {
    vector<int> table = count_factor(N);

    vector<int> alt(N + 1, 0);
    alt[1] = N;
    for (int i = 2; i <= N; i++) {
      alt[i] = N - i;
    }

    for (int i = 2; i <= N; i++) {
      if (table[i] < 0)
        continue;

      for (int j = i; j < N; j += i) {
        if (table[i] % 2) {
          alt[j] -= (N - j) / i;
        } else {
          alt[j] += (N - j) / i;
        }
      }
    }
    return alt;
  }
} // namespace matumoto

#line 2 "math/alternative-totient-table.hpp"

#line 2 "math/base.hpp"

namespace matumoto {
  using namespace std;
  using ll = long long;
} // namespace matumoto
#line 2 "math/count-factor.hpp"

#line 4 "math/count-factor.hpp"

#include <cstdint>
#include <vector>

namespace matumoto {
  vector<int> count_factor(int N) {
    constexpr int INF = INT32_MAX / 2;
    vector<int> table(N + 1, 0);

    for (int i = 2; i <= N; i++) {
      if (table[i])
        continue;
      table[i] = 1;
      for (int j = 2 * i; j <= N; j += i) {
        if (j % (i * i) == 0)
          table[j] = -INF;
        else
          table[j]++;
      }
    }
    return table;
  }
} // namespace matumoto
#line 5 "math/alternative-totient-table.hpp"

#line 7 "math/alternative-totient-table.hpp"

namespace matumoto {
  // Θ(NloglogN)
  vector<int> alternative_totient_table(int N) {
    vector<int> table = count_factor(N);

    vector<int> alt(N + 1, 0);
    alt[1] = N;
    for (int i = 2; i <= N; i++) {
      alt[i] = N - i;
    }

    for (int i = 2; i <= N; i++) {
      if (table[i] < 0)
        continue;

      for (int j = i; j < N; j += i) {
        if (table[i] % 2) {
          alt[j] -= (N - j) / i;
        } else {
          alt[j] += (N - j) / i;
        }
      }
    }
    return alt;
  }
} // namespace matumoto

Back to top page