comp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub luzhiled1333/comp-library

:heavy_check_mark: オイラーのトーシェント関数の列挙
(src/math/totient-enumeration.hpp)

totient_enumeration

std::vector< T > totient_enumeration(T n)

$i$ 番目の要素が $\phi(i)$ であるような長さ $n+1$ の vector を返す。

計算量

関連

math/totient を用いることで、 $\phi(n)$ を $O(\sqrt{n})$ で計算することができる。

Depends on

Verified with

Code

#pragma once

#include "src/cpp-template/header/rep.hpp"

#include <cassert>
#include <limits>
#include <vector>

namespace luz {

  template < typename T >
  std::vector< T > totient_enumeration(T n) {
    static_assert(std::numeric_limits< T >::is_integer,
                  "T must be integer");
    assert(n >= 0);

    n += 1;
    std::vector< T > totients(n);
    for (T i: rep(0, n)) {
      totients[i] = i;
    }
    for (T i: rep(2, n)) {
      if (totients[i] != i) continue;
      for (T j = i; j < n; j += i) {
        totients[j] = totients[j] / i * (i - 1);
      }
    }
    return totients;
  }

} // namespace luz
#line 2 "src/math/totient-enumeration.hpp"

#line 2 "src/cpp-template/header/rep.hpp"

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 4 "src/cpp-template/header/rep.hpp"

#include <algorithm>

namespace luz {

  struct rep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        ++i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rep(const usize f, const usize l) noexcept
        : f(std::min(f, l)),
          l(l) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

  struct rrep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        --i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rrep(const usize f, const usize l) noexcept
        : f(l - 1),
          l(std::min(f, l) - 1) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

} // namespace luz
#line 4 "src/math/totient-enumeration.hpp"

#include <cassert>
#include <limits>
#include <vector>

namespace luz {

  template < typename T >
  std::vector< T > totient_enumeration(T n) {
    static_assert(std::numeric_limits< T >::is_integer,
                  "T must be integer");
    assert(n >= 0);

    n += 1;
    std::vector< T > totients(n);
    for (T i: rep(0, n)) {
      totients[i] = i;
    }
    for (T i: rep(2, n)) {
      if (totients[i] != i) continue;
      for (T j = i; j < n; j += i) {
        totients[j] = totients[j] / i * (i - 1);
      }
    }
    return totients;
  }

} // namespace luz
Back to top page