#line 1 "other-workspace\\tech2.cc" #include #line 2 "Library\\src\\algebra\\modint.hpp" /** * @file modint.hpp * @brief Modular Arithmetic */ #line 11 "Library\\src\\algebra\\modint.hpp" #line 2 "Library\\src\\number_theory\\sqrt_mod.hpp" /** * @file sqrt_mod.hpp * @brief Tonelli-Shanks Algorithm */ #line 2 "Library\\src\\number_theory\\pow_mod.hpp" /** * @file mod_pow.hpp * @brief Modular Exponentiation */ #line 9 "Library\\src\\number_theory\\pow_mod.hpp" #line 2 "Library\\src\\utils\\sfinae.hpp" /** * @file sfinae.hpp * @brief SFINAE */ #line 10 "Library\\src\\utils\\sfinae.hpp" #include #ifndef __INT128_DEFINED__ #ifdef __SIZEOF_INT128__ #define __INT128_DEFINED__ 1 #else #define __INT128_DEFINED__ 0 #endif #endif namespace std { #if __INT128_DEFINED__ template <> struct make_signed<__uint128_t> { using type = __int128_t; }; template <> struct make_signed<__int128_t> { using type = __int128_t; }; template <> struct make_unsigned<__uint128_t> { using type = __uint128_t; }; template <> struct make_unsigned<__int128_t> { using type = __uint128_t; }; template <> struct is_signed<__uint128_t> : std::false_type {}; template <> struct is_signed<__int128_t> : std::true_type {}; template <> struct is_unsigned<__uint128_t> : std::true_type {}; template <> struct is_unsigned<__int128_t> : std::false_type {}; #endif } // namespace std namespace workspace { template struct variadic_front { using type = Tp; }; template struct variadic_back; template struct variadic_back { using type = Tp; }; template struct variadic_back { using type = typename variadic_back::type; }; template class trait> using enable_if_trait_type = typename std::enable_if::value>::type; /** * @brief Return type of subscripting ( @c [] ) access. */ template using subscripted_type = typename std::decay()[0])>::type; template using element_type = typename std::decay()))>::type; template struct has_begin : std::false_type {}; template struct has_begin< _Tp, std::__void_t()))>> : std::true_type { using type = decltype(std::begin(std::declval())); }; template struct has_size : std::false_type {}; template struct has_size<_Tp, std::__void_t()))>> : std::true_type {}; template struct has_resize : std::false_type {}; template struct has_resize<_Tp, std::__void_t().resize( std::declval()))>> : std::true_type {}; template struct has_mod : std::false_type {}; template struct has_mod<_Tp, std::__void_t> : std::true_type {}; template struct is_integral_ext : std::false_type {}; template struct is_integral_ext< _Tp, typename std::enable_if::value>::type> : std::true_type {}; #if __INT128_DEFINED__ template <> struct is_integral_ext<__int128_t> : std::true_type {}; template <> struct is_integral_ext<__uint128_t> : std::true_type {}; #endif #if __cplusplus >= 201402 template constexpr static bool is_integral_ext_v = is_integral_ext<_Tp>::value; #endif template struct multiplicable_uint { using type = uint_least32_t; }; template struct multiplicable_uint< _Tp, typename std::enable_if<(2 < sizeof(_Tp)) && (!__INT128_DEFINED__ || sizeof(_Tp) <= 4)>::type> { using type = uint_least64_t; }; #if __INT128_DEFINED__ template struct multiplicable_uint<_Tp, typename std::enable_if<(4 < sizeof(_Tp))>::type> { using type = __uint128_t; }; #endif template struct multiplicable_int { using type = typename std::make_signed::type>::type; }; template struct multiplicable { using type = std::conditional_t< is_integral_ext<_Tp>::value, std::conditional_t::value, typename multiplicable_int<_Tp>::type, typename multiplicable_uint<_Tp>::type>, _Tp>; }; template struct first_arg { using type = void; }; template struct first_arg<_R(_Tp, _Args...)> { using type = _Tp; }; template struct first_arg<_R (*)(_Tp, _Args...)> { using type = _Tp; }; template struct first_arg<_R (_G::*)(_Tp, _Args...)> { using type = _Tp; }; template struct first_arg<_R (_G::*)(_Tp, _Args...) const> { using type = _Tp; }; template struct parse_compare : first_arg<_Tp> {}; template struct parse_compare<_Tp, std::__void_t> : first_arg {}; template struct get_dimension { static constexpr size_t value = 0; }; template struct get_dimension<_Container, std::enable_if_t::value>> { static constexpr size_t value = 1 + get_dimension::type>::value_type>::value; }; } // namespace workspace #line 11 "Library\\src\\number_theory\\pow_mod.hpp" namespace workspace { /** * @brief Compile time modular exponentiation. * * @param __x * @param __n Exponent * @param __mod Modulus * @return */ template constexpr std::enable_if_t<(is_integral_ext<_Tp>::value), _Tp> pow_mod( _Tp __x, _Tp __n, _Tp __mod) noexcept { assert(__mod > 0); using mul_type = typename multiplicable_uint<_Tp>::type; if ((__x %= __mod) < 0) __x += __mod; mul_type __y{1}; while (__n) { if (__n & 1) (__y *= __x) %= __mod; __x = (mul_type)__x * __x % __mod; __n >>= 1; } return __y; }; } // namespace workspace #line 10 "Library\\src\\number_theory\\sqrt_mod.hpp" namespace workspace { /** * @brief Compile time modular square root. * * @param __x * @param __mod Modulus * @return One if it exists. Otherwise -1. */ template constexpr std::enable_if_t<(is_integral_ext<_Tp>::value), _Tp> sqrt_mod( _Tp __x, _Tp __mod) noexcept { assert(__mod > 0); using mul_type = typename multiplicable_uint<_Tp>::type; if ((__x %= __mod) < 0) __x += __mod; if (!__x) return 0; if (__mod == 2) return __x; if (pow_mod(__x, __mod >> 1, __mod) != 1) return -1; _Tp __z = __builtin_ctz(__mod - 1), __q = __mod >> __z; mul_type __a = pow_mod(__x, (__q + 1) >> 1, __mod), __b = 2; while (pow_mod<_Tp>(__b, __mod >> 1, __mod) == 1) ++__b; __b = pow_mod<_Tp>(__b, __q, __mod); _Tp __shift = 0; for (auto __r = __a * __a % __mod * pow_mod(__x, __mod - 2, __mod) % __mod; __r != 1; (__r *= (__b *= __b) %= __mod) %= __mod) { auto __bsf = __z; for (auto __e = __r; __e != 1; --__bsf) (__e *= __e) %= __mod; while (++__shift != __bsf) (__b *= __b) %= __mod; (__a *= __b) %= __mod; } return __a; }; } // namespace workspace #line 14 "Library\\src\\algebra\\modint.hpp" namespace workspace { namespace _modint_impl { template struct modint { static_assert(is_integral_ext::value, "_Mod must be integral type."); using mod_type = std::make_signed_t, decltype(_Mod)>::type>; using value_type = std::decay_t; using reference = value_type &; using const_reference = value_type const &; using mul_type = typename multiplicable_uint::type; static mod_type mod; // Modulus. static unsigned storage; private: template using modint_if = std::enable_if_t::value, modint>; value_type value = 0; // within [0, mod). struct direct_ctor_t {}; constexpr static direct_ctor_t direct_ctor_tag{}; // Direct constructor template constexpr modint(_Tp __n, direct_ctor_t) noexcept : value(__n) {} public: constexpr modint() noexcept = default; template ::value>> constexpr modint(_Tp __n) noexcept : value((__n %= mod) < _Tp(0) ? static_cast(__n) + mod : static_cast(__n)) {} constexpr modint(bool __n) noexcept : value(__n) {} constexpr operator reference() noexcept { return value; } constexpr operator const_reference() const noexcept { return value; } // unary operators {{ constexpr modint operator++(int) noexcept { modint __t{*this}; operator++(); return __t; } constexpr modint operator--(int) noexcept { modint __t{*this}; operator--(); return __t; } constexpr modint &operator++() noexcept { if (++value == mod) value = 0; return *this; } constexpr modint &operator--() noexcept { if (!value) value = mod - 1; else --value; return *this; } constexpr modint operator+() const noexcept { return *this; } constexpr modint operator-() const noexcept { return {value ? mod - value : 0, direct_ctor_tag}; } // }} unary operators // operator+= {{ constexpr modint &operator+=(const modint &__x) noexcept { if ((value += __x.value) >= mod) value -= mod; return *this; } template constexpr modint_if<_Tp> &operator+=(_Tp __x) noexcept { __x %= mod, value += __x; if (value < 0) value += mod; else if (value >= mod) value -= mod; return *this; } // }} operator+= // operator+ {{ template constexpr modint_if<_Tp> operator+(_Tp const &__x) const noexcept { return modint{*this} += __x; } constexpr modint operator+(modint __x) const noexcept { return __x += *this; } template constexpr friend modint_if<_Tp> operator+(_Tp const &__x, modint __y) noexcept { return __y += __x; } // }} operator+ // operator-= {{ constexpr modint &operator-=(const modint &__x) noexcept { if ((value -= __x.value) < 0) value += mod; return *this; } template constexpr modint_if<_Tp> &operator-=(_Tp __x) noexcept { __x %= mod, value -= __x; if (value < 0) value += mod; else if (value >= mod) value -= mod; return *this; } // }} operator-= // operator- {{ template constexpr modint_if<_Tp> operator-(_Tp const &__x) const noexcept { return modint{*this} -= __x; } constexpr modint operator-(const modint &__x) const noexcept { return modint{*this} -= __x; } template constexpr friend modint_if<_Tp> operator-(_Tp __x, const modint &__y) noexcept { if (((__x -= __y.value) %= mod) < 0) __x += mod; return {__x, direct_ctor_tag}; } // }} operator- // operator*= {{ constexpr modint &operator*=(const modint &__x) noexcept { value = static_cast(value * static_cast(__x.value) % mod); return *this; } template constexpr modint_if<_Tp> &operator*=(_Tp __x) noexcept { value = static_cast( value * ((__x %= mod) < 0 ? mul_type(__x + mod) : mul_type(__x)) % mod); return *this; } // }} operator*= // operator* {{ constexpr modint operator*(const modint &__x) const noexcept { return {static_cast(value) * __x.value % mod, direct_ctor_tag}; } template constexpr modint_if<_Tp> operator*(_Tp __x) const noexcept { __x %= mod; if (__x < 0) __x += mod; return {static_cast(value) * __x % mod, direct_ctor_tag}; } template constexpr friend modint_if<_Tp> operator*(_Tp __x, const modint &__y) noexcept { __x %= mod; if (__x < 0) __x += mod; return {static_cast(__x) * __y.value % mod, direct_ctor_tag}; } // }} operator* protected: static value_type _mem(value_type __x) { static std::vector __m{0, 1}; static value_type __i = (__m.reserve(storage), 1); while (__i < __x) { ++__i; __m.emplace_back(mod - mul_type(mod / __i) * __m[mod % __i] % mod); } return __m[__x]; } static value_type _div(mul_type __r, value_type __x) noexcept { assert(__x != value_type(0)); if (!__r) return 0; std::make_signed_t __v{}; bool __neg = __x < 0 ? __x = -__x, true : false; if (static_cast(__x) < storage) __v = _mem(__x); else { value_type __y{mod}, __u{1}, __t; while (__x) __t = __y / __x, __y ^= __x ^= (__y -= __t * __x) ^= __x, __v ^= __u ^= (__v -= __t * __u) ^= __u; if (__y < 0) __neg ^= 1; } if (__neg) __v = 0 < __v ? mod - __v : -__v; else if (__v < 0) __v += mod; return __r == mul_type(1) ? static_cast(__v) : static_cast(__r * __v % mod); } public: static void reserve(unsigned __n) noexcept { if (storage < __n) storage = __n; } // operator/= {{ constexpr modint &operator/=(const modint &__x) noexcept { if (value) value = _div(value, __x.value); return *this; } template constexpr modint_if<_Tp> &operator/=(_Tp __x) noexcept { if (value) value = _div(value, __x %= mod); return *this; } // }} operator/= // operator/ {{ constexpr modint operator/(const modint &__x) const noexcept { if (!value) return {}; return {_div(value, __x.value), direct_ctor_tag}; } template constexpr modint_if<_Tp> operator/(_Tp __x) const noexcept { if (!value) return {}; return {_div(value, __x %= mod), direct_ctor_tag}; } template constexpr friend modint_if<_Tp> operator/(_Tp __x, const modint &__y) noexcept { if (!__x) return {}; if ((__x %= mod) < 0) __x += mod; return {_div(__x, __y.value), direct_ctor_tag}; } // }} operator/ constexpr modint inv() const noexcept { return _div(1, value); } template constexpr modint pow(_Tp __e) const noexcept { static_assert(not std::is_floating_point<_Tp>::value); modint __r{mod != 1, direct_ctor_tag}; for (modint __b{__e < _Tp(0) ? __e = -__e, _div(1, value) : value, direct_ctor_tag}; __e; __e /= 2, __b *= __b) if (__e % 2) __r *= __b; return __r; } template constexpr friend modint pow(modint __b, _Tp __e) noexcept { static_assert(not std::is_floating_point<_Tp>::value); if (__e < _Tp(0)) { __e = -__e; __b.value = _div(1, __b.value); } modint __r{mod != 1, direct_ctor_tag}; for (; __e; __e /= 2, __b *= __b) if (__e % 2) __r *= __b; return __r; } constexpr modint sqrt() const noexcept { return {sqrt_mod(value, mod), direct_ctor_tag}; } friend constexpr modint sqrt(const modint &__x) noexcept { return {sqrt_mod(__x.value, mod), direct_ctor_tag}; } friend std::istream &operator>>(std::istream &__is, modint &__x) noexcept { std::string __s; __is >> __s; bool __neg = false; if (__s.front() == '-') { __neg = true; __s.erase(__s.begin()); } __x = 0; for (char __c : __s) __x = __x * 10 + (__c - '0'); if (__neg) __x = -__x; return __is; } }; template typename modint<_Mod, _Storage>::mod_type modint<_Mod, _Storage>::mod = _Mod > 0 ? _Mod : 0; template unsigned modint<_Mod, _Storage>::storage = _Storage; } // namespace _modint_impl constexpr unsigned _modint_default_storage = 1 << 24; template 0)>> using modint = _modint_impl::modint<_Mod, _Storage>; template using runtime_modint = _modint_impl::modint<-(signed)_Id, _Storage>; template using runtime_modint64 = _modint_impl::modint<-(int_least64_t)_Id, _Storage>; } // namespace workspace #line 4 "other-workspace\\tech2.cc" namespace workspace { using mint = modint<998244353>; } #line 2 "Library\\src\\utils\\round_div.hpp" /* * @file round_div.hpp * @brief Round Integer Division */ #line 9 "Library\\src\\utils\\round_div.hpp" #line 11 "Library\\src\\utils\\round_div.hpp" namespace workspace { /* * @fn floor_div * @brief floor of fraction. * @param x the numerator * @param y the denominator * @return maximum integer z s.t. z <= x / y * @note y must be nonzero. */ template constexpr typename std::enable_if<(is_integral_ext::value && is_integral_ext::value), typename std::common_type::type>::type floor_div(T1 x, T2 y) { assert(y != 0); if (y < 0) x = -x, y = -y; return x < 0 ? (x - y + 1) / y : x / y; } /* * @fn ceil_div * @brief ceil of fraction. * @param x the numerator * @param y the denominator * @return minimum integer z s.t. z >= x / y * @note y must be nonzero. */ template constexpr typename std::enable_if<(is_integral_ext::value && is_integral_ext::value), typename std::common_type::type>::type ceil_div(T1 x, T2 y) { assert(y != 0); if (y < 0) x = -x, y = -y; return x < 0 ? x / y : (x + y - 1) / y; } } // namespace workspace #line 9 "other-workspace\\tech2.cc" namespace workspace { template auto quotients(_Tp __n) { assert(__n >= 0); std::vector> res; for (_Tp q = __n + 1; q;) { _Tp k = __n / q + 1; q = __n / k; res.emplace_back(k, q); } return res; } void main() { int n; std::cin >> n; std::vector mu(n + 1, 2); mu[0] = 0; mu[1] = 1; for (auto i = 2; i <= n; ++i) { if (mu[i] != 2) continue; for (auto j = i, k = 1; j <= n; j += i, ++k) { if (k % i) mu[j] = -mu[k]; else mu[j] = 0; } } std::vector c(n + 1); mint msum, csum; std::vector pow2(n + 1); pow2[0] = 1; auto pow3i4 = pow2; const auto base = mint(3) / 4; for (auto i = 1; i < pow2.size(); ++i) { pow2[i] = pow2[i - 1] * 2; pow3i4[i] = pow3i4[i - 1] * base; } for (auto i = 1; i <= n; ++i) { msum += mu[i]; c[i] = mu[i] * pow2[n / i]; csum += c[i]; } auto ans = (csum - msum) * (csum - msum); std::vector used(n + 1); for (auto i = 2; i <= n; ++i) { if (not used[i]) { for (auto j = i, k = 1; j <= n; j += i, ++k) { c[j] += c[k]; used[j] = 1; } } else used[i] = 0; } for (auto &x : c) { x *= x; } for (auto i = 1; i <= n; ++i) { if (used[i]) { for (auto k = n / i, j = k * i; j; j -= i, --k) { c[j] -= c[k]; } } ans += c[i] * pow3i4[n / i]; ans -= c[i]; } std::cout << ans << "\n"; } } // namespace workspace int main() { workspace::main(); }