kpr/math/euler_phi.hpp

View this file on GitHub
Last update: 2023-05-30 09:27:18+09:00
Include: #include "kpr/math/euler_phi.hpp"

Depends on

kpr/meta/setting.hpp

Required by

Code

#pragma once
#include <cstdint>
#include "../meta/setting.hpp"

namespace kpr {
    // オイラーのφ関数

    [[maybe_unused]] inline constexpr struct {
        constexpr KYOPRO_BASE_INT operator ()(std::uint_fast64_t n) const noexcept {
            std::uint_fast64_t res = n;
            if ((n & 1) == 0) {
                res -= res >> 1;
                n >>= 1;
                while ((n & 1) == 0) n >>= 1;
            }
            for (std::uint_fast64_t i = 3; i * i <= n; i += 2) {
                if (n % i == 0) {
                res -= res / i;
                n /= i;
                while (n % i == 0) n /= i;
                }
            }
            if (n != 1) res -= res / n;
            return res;
        }
    } euler_phi;
} // namespace kpr

#line 2 "kpr/math/euler_phi.hpp"
#include <cstdint>
#line 3 "kpr/meta/setting.hpp"

#ifndef KYOPRO_BASE_INT
// 基本符号付き整数型

#define KYOPRO_BASE_INT std::int64_t
#endif

#ifndef KYOPRO_BASE_UINT
// 基本符号なし整数型

#define KYOPRO_BASE_UINT std::uint64_t
#endif

#ifndef KYOPRO_BASE_FLOAT
// 基本浮動小数点数型

#define KYOPRO_BASE_FLOAT double
#endif

#ifndef KYOPRO_LL
// ll

#define KYOPRO_LL long long
#endif

#ifndef KYOPRO_LF
// lf

#define KYOPRO_LF double
#endif

#ifndef KYOPRO_MINT
// mint

#define KYOPRO_MINT kpr::ModInt<mod>
#endif

#ifndef KYOPRO_DEFAULT_MOD
// 問題で設定されたmod

#define KYOPRO_DEFAULT_MOD (static_cast<KYOPRO_BASE_UINT>(998244353))
#endif

#ifndef KYOPRO_DECIMAL_PRECISION
// 小数精度(桁)

#define KYOPRO_DECIMAL_PRECISION (static_cast<KYOPRO_BASE_UINT>(12))
#endif

#ifndef KYOPRO_INF_DIV
// 無限大を表す整数が最大値の何分の一かを表す

#define KYOPRO_INF_DIV (static_cast<KYOPRO_BASE_UINT>(3))
#endif

#ifndef KYOPRO_BUFFER_SIZE
// デフォルトのバッファサイズ

#define KYOPRO_BUFFER_SIZE (static_cast<KYOPRO_BASE_UINT>(2048))
#endif

#ifndef KYOPRO_BINOM_MOD_MAX
// デフォルトのBinomModの計算上限

#define KYOPRO_BINOM_MOD_MAX (static_cast<KYOPRO_BASE_UINT>(1000000))
#endif
#line 4 "kpr/math/euler_phi.hpp"

namespace kpr {
    // オイラーのφ関数

    [[maybe_unused]] inline constexpr struct {
        constexpr KYOPRO_BASE_INT operator ()(std::uint_fast64_t n) const noexcept {
            std::uint_fast64_t res = n;
            if ((n & 1) == 0) {
                res -= res >> 1;
                n >>= 1;
                while ((n & 1) == 0) n >>= 1;
            }
            for (std::uint_fast64_t i = 3; i * i <= n; i += 2) {
                if (n % i == 0) {
                res -= res / i;
                n /= i;
                while (n % i == 0) n /= i;
                }
            }
            if (n != 1) res -= res / n;
            return res;
        }
    } euler_phi;
} // namespace kpr