unit-test/math/totient-enumeration.test.cpp

• View this file on GitHub
• Last update: 2023-07-30 00:54:52+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/ITP1_1_A

Depends on

• int alias (src/cpp-template/header/int-alias.hpp)
• rep 構造体 (src/cpp-template/header/rep.hpp)
• size alias (src/cpp-template/header/size-alias.hpp)
• オイラーのトーシェント関数の列挙 (src/math/totient-enumeration.hpp)

Code

// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/ITP1_1_A

#include "src/math/totient-enumeration.hpp"

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

#include <cassert>
#include <iostream>
#include <numeric>
#include <vector>

namespace luz {

  u32 naive_totient(u32 n) {
    u32 result = 0;
    for (u32 m: rep(1, n + 1)) {
      if (std::gcd(n, m) == 1) result++;
    }
    return result;
  }

  void main_() {
    std::vector< u32 > totients = totient_enumeration((u32)1000);

    for (u32 i: rep(0, 1001)) {
      assert(totients[i] == naive_totient(i));
    }

    std::cout << "Hello World" << std::endl;
  }

} // namespace luz

int main() {
  luz::main_();
}

#line 1 "unit-test/math/totient-enumeration.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/ITP1_1_A

#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
#line 4 "unit-test/math/totient-enumeration.test.cpp"

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

#include <cstdint>

namespace luz {

  using i32  = std::int32_t;
  using i64  = std::int64_t;
  using i128 = __int128_t;

  using u32  = std::uint32_t;
  using u64  = std::uint64_t;
  using u128 = __uint128_t;

} // namespace luz
#line 7 "unit-test/math/totient-enumeration.test.cpp"

#line 9 "unit-test/math/totient-enumeration.test.cpp"
#include <iostream>
#include <numeric>
#line 12 "unit-test/math/totient-enumeration.test.cpp"

namespace luz {

  u32 naive_totient(u32 n) {
    u32 result = 0;
    for (u32 m: rep(1, n + 1)) {
      if (std::gcd(n, m) == 1) result++;
    }
    return result;
  }

  void main_() {
    std::vector< u32 > totients = totient_enumeration((u32)1000);

    for (u32 i: rep(0, 1001)) {
      assert(totients[i] == naive_totient(i));
    }

    std::cout << "Hello World" << std::endl;
  }

} // namespace luz

int main() {
  luz::main_();
}

Back to top page