unit-test/math/totient.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)
• オイラーのトーシェント関数 (オイラーの $\phi$ 関数, Euler's totient function) (src/math/totient.hpp)

Code

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

#include "src/math/totient.hpp"

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

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

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_() {

    // small
    for (u32 i: rep(0, 1000)) {
      assert(totient(i) == naive_totient(i));
    }

    // large
    assert(totient(735134400) == 132710400);
    assert(totient(1000000007) == 1000000006);
    assert(totient(1000000009) == 1000000008);
    assert(totient(31415926535) == 20847434400);

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

} // namespace luz

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

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

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

#include <cassert>
#include <limits>

namespace luz {

  template < typename T >
  T totient(T n) {
    static_assert(std::numeric_limits< T >::is_integer,
                  "T must be integer");
    assert(n >= 0);
    T t = n, p = 2;
    while (p * p <= n) {
      if (n % p == 0) {
        t -= t / p;
        while (n % p == 0) {
          n /= p;
        }
      }
      p++;
    }
    if (n > 1) {
      t -= t / n;
    }
    return t;
  }

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

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

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_() {

    // small
    for (u32 i: rep(0, 1000)) {
      assert(totient(i) == naive_totient(i));
    }

    // large
    assert(totient(735134400) == 132710400);
    assert(totient(1000000007) == 1000000006);
    assert(totient(1000000009) == 1000000008);
    assert(totient(31415926535) == 20847434400);

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

} // namespace luz

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

Back to top page