#ifndef KK2_TEMPLATE_PROCON_HPP #define KK2_TEMPLATE_PROCON_HPP 1 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifndef KK2_TEMPLATE_CONSTANT_HPP #define KK2_TEMPLATE_CONSTANT_HPP 1 #ifndef KK2_TEMPLATE_TYPE_ALIAS_HPP #define KK2_TEMPLATE_TYPE_ALIAS_HPP 1 #include #include #include #include using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; using pi = std::pair; using pl = std::pair; using pil = std::pair; using pli = std::pair; template using vc = std::vector; template using vvc = std::vector>; template using vvvc = std::vector>; template using vvvvc = std::vector>; template using pq = std::priority_queue; template using pqi = std::priority_queue, std::greater>; #endif // KK2_TEMPLATE_TYPE_ALIAS_HPP // #include "type_alias.hpp" template constexpr T infty = 0; template <> constexpr int infty = (1 << 30) - 123; template <> constexpr i64 infty = (1ll << 62) - (1ll << 31); template <> constexpr i128 infty = (i128(1) << 126) - (i128(1) << 63); template <> constexpr u32 infty = infty; template <> constexpr u64 infty = infty; template <> constexpr u128 infty = infty; template <> constexpr double infty = infty; template <> constexpr long double infty = infty; constexpr int mod = 998244353; constexpr int modu = 1e9 + 7; constexpr long double PI = 3.14159265358979323846; #endif // KK2_TEMPLATE_CONSTANT_HPP // #include "constant.hpp" #ifndef KK2_TEMPLATE_FUNCTION_UTIL_HPP #define KK2_TEMPLATE_FUNCTION_UTIL_HPP 1 #include #include namespace kk2 { template auto make_vector(int first, Sizes... sizes) { if constexpr (sizeof...(sizes) == 0) { return std::vector(first); } else { return std::vector(sizes...))>(first, make_vector(sizes...)); } } template void fill_all(std::vector &v, const U &x) { std::fill(std::begin(v), std::end(v), T(x)); } template void fill_all(std::vector> &v, const U &x) { for (auto &u : v) fill_all(u, x); } template int mysize(const C &c) { return c.size(); } // T: comutative monoid template U all_sum(const std::vector &v, U init, U = U()) { U res = init; for (const auto &x : v) res += x; return res; } template U all_sum(const std::vector> &v, U init, U unit = U()) { U res = init; for (const auto &u : v) res += all_sum(u, unit, unit); return res; } // T: commutative monoid, F: (U, T) -> U template U all_prod(const std::vector &v, U init, const F &f, U = U()) { U res = init; for (const auto &x : v) res = f(res, x); return res; } template U all_prod(const std::vector> &v, U init, const F &f, U unit) { U res = init; for (const auto &u : v) res = f(res, all_prod(u, unit, f, unit)); return res; } template T all_min(const std::vector &v) { if (v.empty()) return T(); T res = v[0]; for (const auto &x : v) res = res > x ? x : res; return res; } template T all_min(const std::vector> &v) { T res{}; bool first = true; for (const auto &u : v) { if (u.empty()) continue; if (first) { res = all_min(u); first = false; } else { T tmp = all_min(u); res = res > tmp ? tmp : res; } } return res; } template T all_max(const std::vector &v) { if (v.empty()) return T(); T res = v[0]; for (const auto &x : v) res = res < x ? x : res; return res; } template T all_max(const std::vector> &v) { T res{}; bool first = true; for (const auto &u : v) { if (u.empty()) continue; if (first) { res = all_max(u); first = false; } else { T tmp = all_max(u); res = res < tmp ? tmp : res; } } return res; } } // namespace kk2 #endif // KK2_TEMPLATE_FUNCTION_UTIL_HPP // #include "function_util.hpp" #ifndef KK2_TEMPLATE_IO_UTIL_HPP #define KK2_TEMPLATE_IO_UTIL_HPP 1 #include #include #include #ifndef KK2_TYPE_TRAITS_TYPE_TRAITS_HPP #define KK2_TYPE_TRAITS_TYPE_TRAITS_HPP 1 #include #include #include namespace kk2 { #ifndef _MSC_VER template using is_signed_int128 = typename std::conditional::value or std::is_same::value, std::true_type, std::false_type>::type; template using is_unsigned_int128 = typename std::conditional::value or std::is_same::value, std::true_type, std::false_type>::type; template using is_integral = typename std::conditional::value or is_signed_int128::value or is_unsigned_int128::value, std::true_type, std::false_type>::type; template using is_signed = typename std::conditional::value or is_signed_int128::value, std::true_type, std::false_type>::type; template using is_unsigned = typename std::conditional::value or is_unsigned_int128::value, std::true_type, std::false_type>::type; template using make_unsigned_int128 = typename std::conditional::value, __uint128_t, unsigned __int128>; template using to_unsigned = typename std::conditional::value, make_unsigned_int128, typename std::conditional::value, std::make_unsigned, std::common_type>::type>::type; #else template using is_integral = std::enable_if_t::value>; template using is_signed = std::enable_if_t::value>; template using is_unsigned = std::enable_if_t::value>; template using to_unsigned = std::make_unsigned; #endif // _MSC_VER template using is_integral_t = std::enable_if_t::value>; template using is_signed_t = std::enable_if_t::value>; template using is_unsigned_t = std::enable_if_t::value>; template using is_function_pointer = typename std::conditional && std::is_function_v>, std::true_type, std::false_type>::type; template ::value> * = nullptr> struct is_two_args_function_pointer : std::false_type {}; template struct is_two_args_function_pointer : std::true_type {}; template using is_two_args_function_pointer_t = std::enable_if_t::value>; namespace type_traits { struct istream_tag {}; struct ostream_tag {}; } // namespace type_traits template using is_standard_istream = typename std::conditional::value || std::is_same::value, std::true_type, std::false_type>::type; template using is_standard_ostream = typename std::conditional::value || std::is_same::value, std::true_type, std::false_type>::type; template using is_user_defined_istream = std::is_base_of; template using is_user_defined_ostream = std::is_base_of; template using is_istream = typename std::conditional::value || is_user_defined_istream::value, std::true_type, std::false_type>::type; template using is_ostream = typename std::conditional::value || is_user_defined_ostream::value, std::true_type, std::false_type>::type; template using is_istream_t = std::enable_if_t::value>; template using is_ostream_t = std::enable_if_t::value>; } // namespace kk2 #endif // KK2_TYPE_TRAITS_TYPE_TRAITS_HPP // #include "../type_traits/type_traits.hpp" // なんかoj verifyはプロトタイプ宣言が落ちる namespace impl { struct read { template static void all_read(IStream &is, T &x) { is >> x; } template static void all_read(IStream &is, std::pair &p) { all_read(is, p.first); all_read(is, p.second); } template static void all_read(IStream &is, std::vector &v) { for (T &x : v) all_read(is, x); } template static void all_read(IStream &is, std::array &a) { for (T &x : a) all_read(is, x); } }; struct write { template static void all_write(OStream &os, const T &x) { os << x; } template static void all_write(OStream &os, const std::pair &p) { all_write(os, p.first); all_write(os, ' '); all_write(os, p.second); } template static void all_write(OStream &os, const std::vector &v) { for (int i = 0; i < (int)v.size(); ++i) { if (i) all_write(os, ' '); all_write(os, v[i]); } } template static void all_write(OStream &os, const std::array &a) { for (int i = 0; i < (int)F; ++i) { if (i) all_write(os, ' '); all_write(os, a[i]); } } }; } // namespace impl template * = nullptr> IStream &operator>>(IStream &is, std::pair &p) { impl::read::all_read(is, p); return is; } template * = nullptr> IStream &operator>>(IStream &is, std::vector &v) { impl::read::all_read(is, v); return is; } template * = nullptr> IStream &operator>>(IStream &is, std::array &a) { impl::read::all_read(is, a); return is; } template * = nullptr> OStream &operator<<(OStream &os, const std::pair &p) { impl::write::all_write(os, p); return os; } template * = nullptr> OStream &operator<<(OStream &os, const std::vector &v) { impl::write::all_write(os, v); return os; } template * = nullptr> OStream &operator<<(OStream &os, const std::array &a) { impl::write::all_write(os, a); return os; } #endif // KK2_TEMPLATE_IO_UTIL_HPP // #include "io_util.hpp" #ifndef KK2_TEMPLATE_MACROS_HPP #define KK2_TEMPLATE_MACROS_HPP 1 #define rep1(a) for (long long _ = 0; _ < (long long)(a); ++_) #define rep2(i, a) for (long long i = 0; i < (long long)(a); ++i) #define rep3(i, a, b) for (long long i = (a); i < (long long)(b); ++i) #define repi2(i, a) for (long long i = (a) - 1; i >= 0; --i) #define repi3(i, a, b) for (long long i = (a) - 1; i >= (long long)(b); --i) #define overload3(a, b, c, d, ...) d #define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define repi(...) overload3(__VA_ARGS__, repi3, repi2, rep1)(__VA_ARGS__) #define fi first #define se second #define all(p) p.begin(), p.end() #endif // KK2_TEMPLATE_MACROS_HPP // #include "macros.hpp" // #include "type_alias.hpp" struct FastIOSetUp { FastIOSetUp() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } fast_io_set_up; auto &kin = std::cin; auto &kout = std::cout; auto (*kendl)(std::ostream &) = std::endl>; void Yes(bool b = 1) { kout << (b ? "Yes\n" : "No\n"); } void No(bool b = 1) { kout << (b ? "No\n" : "Yes\n"); } void YES(bool b = 1) { kout << (b ? "YES\n" : "NO\n"); } void NO(bool b = 1) { kout << (b ? "NO\n" : "YES\n"); } void yes(bool b = 1) { kout << (b ? "yes\n" : "no\n"); } void no(bool b = 1) { kout << (b ? "no\n" : "yes\n"); } template inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); } template inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); } std::istream &operator>>(std::istream &is, u128 &x) { std::string s; is >> s; x = 0; for (char c : s) { assert('0' <= c && c <= '9'); x = x * 10 + c - '0'; } return is; } std::istream &operator>>(std::istream &is, i128 &x) { std::string s; is >> s; bool neg = s[0] == '-'; x = 0; for (int i = neg; i < (int)s.size(); i++) { assert('0' <= s[i] && s[i] <= '9'); x = x * 10 + s[i] - '0'; } if (neg) x = -x; return is; } std::ostream &operator<<(std::ostream &os, u128 x) { if (x == 0) return os << '0'; std::string s; while (x) { s.push_back('0' + x % 10); x /= 10; } std::reverse(s.begin(), s.end()); return os << s; } std::ostream &operator<<(std::ostream &os, i128 x) { if (x == 0) return os << '0'; if (x < 0) { os << '-'; x = -x; } std::string s; while (x) { s.push_back('0' + x % 10); x /= 10; } std::reverse(s.begin(), s.end()); return os << s; } #endif // KK2_TEMPLATE_PROCON_HPP // #include // #include #ifndef KK2_MATH_SQRT_FLOOR_HPP #define KK2_MATH_SQRT_FLOOR_HPP 1 #include #ifndef KK2_MATH_FRAC_FLOOR_HPP #define KK2_MATH_FRAC_FLOOR_HPP 1 #include namespace kk2 { // floor(x) = ceil(x) - 1 (for all x not in Z) ...(1) // floor(x) = -ceil(-x) (for all x) ...(2) // return floor(a / b) template constexpr T fracfloor(T a, U b) { assert(b != 0); if (a % b == 0) return a / b; if (a >= 0) return a / b; // floor(x) = -ceil(-x) by (2) // = -floor(-x) - 1 by (1) return -((-a) / b) - 1; } // return ceil(a / b) template constexpr T fracceil(T a, U b) { assert(b != 0); if (a % b == 0) return a / b; if (a >= 0) return a / b + 1; // ceil(x) = -floor(-x) by (2) return -((-a) / b); } } // namespace kk2 #endif // KK2_MATH_FRAC_FLOOR_HPP // #include "frac_floor.hpp" namespace kk2 { template T sqrt_floor(T n) { assert(n >= 0); if (n == T(0)) return 0; T x = std::sqrt(n); if (x == T(0)) ++x; while (x > kk2::fracfloor(n, x)) --x; while (x + 1 <= kk2::fracfloor(n, x + 1)) ++x; return x; } template T sqrt_ceil(T n) { assert(n >= 0); if (n <= T(1)) return n; T x = std::sqrt(n); if (x == T(0)) ++x; while (x < kk2::fracceil(n, x)) ++x; while (x - 1 >= kk2::fracceil(n, x - 1)) --x; return x; } } // namespace kk2 #endif // KK2_MATH_SQRT_FLOOR_HPP // #include using namespace std; void solve() { i64 n; kin >> n; int sqrt_n = kk2::sqrt_floor(n); kout << sqrt_n + n / (sqrt_n + 1) << endl; } int main() { int t = 1; // kin >> t; rep (t) solve(); return 0; } // converted!! // Author: kk2 // 2025-01-31 14:25:24