結果
| 問題 |
No.1664 Unstable f(n)
|
| コンテスト | |
| ユーザー |
 π
|
| 提出日時 | 2021-09-03 23:28:09 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 32,070 bytes |
| コンパイル時間 | 1,714 ms |
| コンパイル使用メモリ | 130,244 KB |
| 実行使用メモリ | 6,824 KB |
| 最終ジャッジ日時 | 2024-12-15 18:23:51 |
| 合計ジャッジ時間 | 2,776 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 26 WA * 12 |
ソースコード
#define NDEBUG 1
//#pragma GCC optimize("O3")
#pragma GCC target("avx")
//#pragma GCC optimize("unroll-loops")
#define FOR(i, s, e) for(auto i = (s); i < (e); ++i)
#define REP(i, e) FOR(i, decltype(e)(), (e))
#define ALL(x) (std::begin(x)),(std::end(x))
#ifndef MOD
#define MOD 1000000007
#endif // ! MOD
#include <cstdint>
#include <cstddef>
#include <limits>
#if __cplusplus > 201703L && __cpp_concepts >= 201907L
#include <concepts>
#else
#include <type_traits>
#define NO_CONCEPT
#endif // __has_include(<concepts>)
#include <iterator>
#include <utility>
#include <algorithm>
#include <initializer_list>
#include <tuple>
#include <string_view>
#include <string>
#include <array>
#include <vector>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>
#include <list>
#include <stack>
#include <queue>
namespace nlib {
#ifdef NO_CONCEPT
template <class T, class U> struct is_super_type : std::conjunction<std::is_same<std::common_type_t<T, U>, T>, std::is_same<std::common_type_t<T, U>, std::common_type_t<U, T>>> {};
template <class T, class U> inline constexpr bool is_super_type_v = is_super_type<T, U>::value;
#else
template <class T, class U>
concept super_type = std::same_as<std::common_type_t<T, U>, T> && std::same_as<std::common_type_t<U, T>, T>;
#endif // NO_CONCEPT
namespace {
using swallow = std::initializer_list<int>;
} // namespace
using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
template <class T> using vector = std::vector<T>;
template <class T> using deque = std::deque<T>;
template <class T> using unordered_set = std::unordered_set<T>;
template <class T, class U> using unordered_map = std::unordered_map<T, U>;
template <class T> using forward_list = std::forward_list<T>;
template <class T> using list = std::list<T>;
template <class T, class Container = deque<T>> using stack = std::stack<T, Container>;
template <class T, class Container = deque<T>> using queue = std::queue<T, Container>;
template <class T, class Container = vector<T>, class Compare = std::less<typename Container::value_type>> using priority_queue = std::priority_queue<T, Container, Compare>;
template <class T, size_t n> using array = std::array<T, n>;
using string = std::string;
using string_view = std::string_view;
template <class T> using vecvec = vector<vector<T>>;
using vi = vector<int>;
template <size_t n> using ai = array<int, n>;
template<class T> using vvi = vecvec<int>;
template <size_t n> using vai = vector<array<int, n>>;
template <size_t n, size_t m = n> using aai = array<array<int, m>, n>;
using vl = vector<ll>;
template <size_t n> using al = array<ll, n>;
using vvl = vecvec<ll>;
template <size_t n> using val = vector<array<ll, n>>;
template <size_t n, size_t m = n> using aal = array<array<ll, m>, n>;
using vs = vector<string>;
template <size_t n> using as = array<string, n>;
template <size_t n> using asv = array<string_view, n>;
using namespace std::literals;
inline constexpr string_view alnums = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"sv;
inline constexpr string_view digits = alnums.substr(0, 10);
inline constexpr string_view l_alphas = alnums.substr(10, 26);
inline constexpr string_view g_alphas = alnums.substr(36, 26);
inline constexpr string_view alphas = alnums.substr(10, 52);
inline constexpr auto mod = MOD;
} // namespace nlib
#include <cmath>
namespace nlib {
template <class T = int, class U = ll, T m = mod>
class mod_int {
T _value;
public:
static constexpr T mod = m;
// TODO
/*
static constexpr mod_int get_inverse(T v) {
}
constexpr mod_int& inverse() {
value = get_inverse(value);
return *this;
}
*/
constexpr mod_int() noexcept = default;
constexpr mod_int(const mod_int& v) noexcept = default;
constexpr mod_int(mod_int&& v) noexcept = default;
constexpr mod_int(const T& v) noexcept: _value(static_cast<T>(v) % mod) {
if(_value < 0) _value += mod;
}
#ifdef NO_CONCEPT
template<class X, class = std::enable_if_t<!is_super_type_v<T, X>>>
#else
template<class X> requires (!super_type<T, X>)
#endif // ! NO_CONCEPT
constexpr mod_int(const X& v) noexcept: _value(static_cast<T>(v % static_cast<X>(mod))) {
if(_value < 0) _value += mod;
}
#if __cplusplus > 201703L
constexpr
#endif // c++2a
~mod_int() noexcept = default;
constexpr operator T() const noexcept {return _value;}
#define DEFOP(op) constexpr mod_int& operator op noexcept
DEFOP(=(const mod_int& v) &) = default;
DEFOP(=(mod_int&& v) &) = default;
DEFOP(++()) {
if(_value == std::numeric_limits<mod_int>::max()) _value = 0;
else ++_value;
return *this;
}
DEFOP(--()) {
if(_value == 0) _value = std::numeric_limits<mod_int>::max();
else --_value;
return *this;
}
DEFOP(+=(const mod_int& v)) {
if((_value += v._value) >= mod) _value -= mod;
return *this;
}
DEFOP(-=(const mod_int& v)) {
if((_value -= v._value) < 0) _value += mod;
return *this;
}
DEFOP(*=(const mod_int& v)) {
_value = static_cast<T>((static_cast<U>(_value) * static_cast<U>(v._value)) % static_cast<U>(mod));
return *this;
}
DEFOP(/=(const mod_int& v)) {
return *this *= inverse(v._value);
}
DEFOP(%=(const mod_int& v)) {
return *this %= v._value;
}
#undef DEFOP
#define DEFOP(op) constexpr mod_int operator op noexcept
DEFOP(++(int)) {mod_int v = *this; ++(*this); return v;}
DEFOP(--(int)) {mod_int v = *this; --(*this); return v;}
DEFOP(+() const) {return *this;}
DEFOP(-() const) {mod_int mint; if(_value) mint._value = mod - _value; return mint;}
#undef DEFOP
explicit constexpr operator bool() const noexcept {return _value;}
constexpr bool operator!() const noexcept {return !_value;}
#define MINT_T class X, class Y, X x
#define MINT mod_int<X, Y, x>
#define TEMPL template <MINT_T>
#ifdef NO_CONCEPT
#define TEMPL_CONV template <MINT_T, class I>
#else
#define TEMPL_CONV template <MINT_T, class I> requires (std::convertible_to<I, MINT>)
#endif // NO_CONCEPT
#ifdef NO_CONCEPT
#define CONV_R(...) std::enable_if_t<std::is_convertible_v<I, MINT>, __VA_ARGS__>
#else
#define CONV_R(...) __VA_ARGS__
#endif // NO_CONCEPT
#define DECOP(r, op) \
TEMPL friend constexpr r operator op(const MINT&, const MINT&) noexcept; \
TEMPL_CONV friend constexpr CONV_R(r) operator op(const MINT&, const I&) noexcept; \
TEMPL_CONV friend constexpr CONV_R(r) operator op(const I&, const MINT&) noexcept;
DECOP(MINT, +)
DECOP(MINT, -)
DECOP(MINT, *)
DECOP(MINT, /)
DECOP(MINT, %)
DECOP(bool, ==)
DECOP(bool, !=)
DECOP(bool, <)
DECOP(bool, >)
DECOP(bool, <=)
DECOP(bool, >=)
#undef DECOP
#undef MINT
};
} // namespace nlib
#define MINT nlib::mod_int<X, Y, x>
#define DEFOP(ret, op, exp0, exp1, exp2) \
TEMPL constexpr ret operator op(const MINT& l, const MINT& r) noexcept {return exp0;} \
TEMPL_CONV constexpr CONV_R(ret) operator op(const MINT& l, const I& r) noexcept {return exp1;} \
TEMPL_CONV constexpr CONV_R(ret) operator op(const I& l, const MINT& r) noexcept {return exp2;}
#define DEFOP_A(op) DEFOP(MINT, op, MINT(l) op##= r, MINT(r) op##= l, MINT(l) op##= r)
DEFOP_A(+)
DEFOP_A(-)
DEFOP_A(*)
DEFOP_A(/)
DEFOP_A(%)
#undef DEFOP_A
#define DEFOP_C(op) DEFOP(bool, op, l._value op r._value, l._value op MINT(r)._value, MINT(l)._value op r._value)
DEFOP_C(==)
DEFOP_C(!=)
DEFOP_C(<)
DEFOP_C(>)
DEFOP_C(<=)
DEFOP_C(>=)
#undef DEFOP_C
#undef DEFOP
#undef CONV_R
#undef TEMPL_CONV
namespace std {
TEMPL struct is_integral<MINT> : true_type {};
TEMPL struct is_signed<MINT> : false_type {};
TEMPL struct numeric_limits<MINT> : numeric_limits<X> {
static constexpr MINT min() noexcept {return 0;}
static constexpr MINT lowest() noexcept {return 0;}
static constexpr MINT max() noexcept {return x - 1;}
static constexpr int digits10 = std::floor(std::log10<X>(static_cast<X>(max())));
static constexpr bool is_signed = false;
static constexpr bool is_modulo = true;
};
} // namespace std
#undef MINT
#undef TEMPL
#undef MINT_T
#include <unistd.h>
#include <cstring>
#include <cmath>
namespace nlib {
#ifndef NO_CONCEPT
template <class T> concept integer_class = std::integral<T> && !std::same_as<T, char> && !std::same_as<T, bool>;
template <class T> concept container_input_or_output = requires(const T x) {
std::begin(x);
std::end(x);
requires std::sentinel_for<decltype(std::end(x)), decltype(std::begin(x))>;
};
template <class T> concept container_forward = container_input_or_output<T> && requires(const T x) {
{std::begin(x)} -> std::forward_iterator;
};
template <class T> concept container_output = container_input_or_output<T> && requires(T x) {
requires std::output_iterator<decltype(std::begin(x)), typename std::iterator_traits<decltype(std::begin(x))>::value_type>;
};
template <class T> concept string_output = container_input_or_output<T> && requires(T& x, const char* s, const char* e) {
requires std::same_as<typename std::iterator_traits<decltype(std::begin(x))>::value_type, char>;
{x.clear()} noexcept;
x.insert(std::end(x), s, e);
};
template <class T> concept string_input = requires(T& x) {
{std::data(x)} noexcept -> std::convertible_to<const char*>;
{std::size(x)} noexcept -> std::convertible_to<size_t>;
};
template <class... Args> concept noonly_one = requires() {
requires sizeof...(Args) != 1;
};
#endif // NO_CONCEPT
inline constexpr char endl = '\n';
inline constexpr char wspc = ' ';
class reader {
public:
static constexpr size_t max_size = 4096;
private:
char buf[max_size];
size_t buf_size = 0, pt = 0;
int fd = -1;
public:
reader() noexcept = default;
reader(const reader&) = delete;
reader(reader&&) noexcept = default;
reader(int open_fd) noexcept : fd(open_fd) {}
reader& operator=(const reader&) noexcept = delete;
reader& operator=(reader&&) noexcept = default;
void open(int open_fd) noexcept {
if(fd != -1) fd = open_fd;
}
size_t read(char* str, size_t size) noexcept {
ssize_t s = ::read(fd, str, size);
return s == -1 ? 0 : size_t(s);
}
bool check() noexcept {return pt >= buf_size && reread();}
bool reread() noexcept {if(buf_size >= max_size) {buf_size = 0;} pt = buf_size; buf_size += read(buf, max_size - pt); return buf_size == pt;}
size_t size() const noexcept {return buf_size - pt;}
bool getc(char& c) noexcept {if(check()) {return true;} c = buf[pt++]; return false;}
template <class T>
#ifdef NO_CONCEPT
auto
#else
requires string_output<T> bool
#endif // NO_CONCEPT
getline(T& s) noexcept
# ifdef NO_CONCEPT
-> decltype(std::begin(s), std::end(s), (s).clear(), s.insert(std::end(s), buf + pt, buf + pt), *this)
# endif // NO_CONCEPT
{
s.clear();
if(check()) return true;
size_t p = pt;
for(;;) {
if(p == buf_size) {
s.insert(std::end(s), buf + pt, buf + p);
if(buf_size != max_size || reread()) return true;
p = 0;
} else if(buf[p] == endl) {
s.insert(std::end(s), buf + pt, buf + p);
pt = p + 1;
return false;
}
++p;
}
}
bool readspace() noexcept {
if(check()) return true;
while(buf[pt] == wspc || buf[pt] == endl) {
++pt;
if(pt == buf_size && (buf_size != max_size || reread())) return true;
}
return false;
}
#ifndef NO_SCAN
reader& scan(char& c) noexcept {if(getc(c)) c = '\0'; return *this;}
template <class T>
# ifdef NO_CONCEPT
std::enable_if_t<std::is_integral_v<T> && (!std::is_same_v<T, char>) && (!std::is_same_v<T, bool>), reader&>
# else
requires integer_class<T> reader&
# endif // NO_CONCEPT
scan(T& n) noexcept {
constexpr T ten = 10;
n = T();
if(readspace()) return *this;
bool sign = false;
switch(buf[pt]) {
case '-':
sign = true;
[[fallthrough]];
case '+':
++pt;
if(check()) return *this;
}
while('0' <= buf[pt] && buf[pt] <= '9') {
n *= ten;
n += T(buf[pt++] - '0');
if(check()) goto end;
}
end:
if(sign) n = -n;
return *this;
}
template <class T>
# ifdef NO_CONCEPT
std::enable_if_t<std::is_floating_point_v<T>, reader&>
# else
requires std::floating_point<T> reader&
# endif // NO_CONCEPT
scan(T& n) noexcept {
constexpr T ten = 10;
n = T();
if(readspace()) return *this;
bool sign = false;
switch(buf[pt]) {
case '-':
sign = true;
[[fallthrough]];
case '+':
++pt;
if(check()) return *this;
}
while('0' <= buf[pt] && buf[pt] <= '9') {
n *= ten;
n += T(buf[pt++] - '0');
if(check()) goto end;
}
if(buf[pt] == '.') {
++pt;
if(check()) goto end;
T pow10 = 1;
while('0' <= buf[pt] && buf[pt] <= '9') {
pow10 *= ten;
if(std::isinf<T>(pow10)) {
do {
++pt;
} while(!check() && '0' <= buf[pt] && buf[pt] <= '9');
goto end;
}
n += T(buf[pt++] - '0') / pow10;
if(check()) goto end;
}
}
end:
if(sign) n = -n;
return *this;
}
template <class C>
# ifdef NO_CONCEPT
auto
# else
requires (container_output<C> && !string_output<C>) reader&
# endif // NO_CONCEPT
scan(C& v) noexcept
# ifdef NO_CONCEPT
-> decltype(std::begin(v), std::end(v), *this)
# endif // NO_CONCEPT
{for(auto& e : v) scan(e); return *this;}
template <class T, size_t N>
# ifdef NO_CONCEPT
std::enable_if_t<is_super_type_v<char, T>, reader&>
# else
requires (!string_output<T[N]>) reader&
# endif // NO_CONCEPT
scan(T (&v)[N]) noexcept {for(T& e : v) scan(e); return *this;}
template <class T>
# ifdef NO_CONCEPT
auto
# else
requires string_output<T> reader&
# endif // ! NO_CONCEPT
scan(T& s) noexcept
# ifdef NO_CONCEPT
-> std::enable_if_t<!std::is_same_v<std::iterator_traits<decltype(std::begin(s))>::value_type, char>,
decltype(std::end(s), (s).clear(), s.insert(std::end(s), buf + pt, buf + pt), *this)>
# endif // NO_CONCEPT
{
s.clear();
if(check()) return *this;
size_t p = pt;
for(;;) {
if(p == buf_size) {
s.insert(std::end(s), buf + pt, buf + p);
if(buf_size != max_size || reread()) return *this;
p = 0;
} else if(buf[p] == wspc || buf[p] == endl) {
s.insert(std::end(s), buf + pt, buf + p);
pt = p + 1;
return *this;
}
++p;
}
return *this;
}
template <class... Args>
# ifdef NO_CONCEPT
std::enable_if_t<sizeof...(Args) != 1, reader&>
# else
requires noonly_one<Args...> reader&
# endif // NO_CONCEPT
scan(Args&... args) noexcept {(void)swallow{(scan(args), 0)...}; return *this;}
#endif // ! NO_SCAN
};
#ifndef UNSET_STDIN
reader rd(0);
# ifndef NO_SCAN
template <class... Args> reader& scan(Args&... args) noexcept {return rd.scan(args...);}
template <class T> T get_v() noexcept {T x; scan(x); return x;}
template <class T> T&& get_v(T&& x) noexcept {scan(x); return std::move(x);}
# endif // ! NO_SCAN
#endif // ! UNSET_STDIN
class writer {
public:
static constexpr size_t max_size = 4096;
private:
char buf[max_size];
size_t pt = 0;
int fd = -1;
#ifndef NO_PRINT
bool iscontinued = false;
#endif // ! NO_PRINT
public:
writer() noexcept = default;
writer(const writer&) = delete;
writer(writer&&) noexcept = default;
writer(int open_fd) noexcept : fd(open_fd) {}
~writer() noexcept {write(buf, pt);}
writer& operator=(const writer&) = delete;
writer& operator=(writer&&) & noexcept = default;
void write(const char* str, size_t size) noexcept {
::write(fd, str, size);
}
void flush() noexcept {
write(buf, pt);
pt = 0;
}
void reopen(int open_fd) noexcept {
if(pt) flush();
fd = open_fd;
}
void check() noexcept {
if(pt >= max_size) {
write(buf, max_size);
pt = 0;
}
}
void putc(const char& c) noexcept {buf[pt] = c;++pt;check();}
void puts(const char* str, size_t len) noexcept {
if(!len) return;
size_t write_size = max_size - pt;
size_t copy_size = len;
if(copy_size <= write_size) {
memcpy(buf + pt, str, copy_size);
pt += copy_size;
check();
} else {
if(pt) {
memcpy(buf + pt, str, write_size);
write(buf, max_size);
} else {
write_size = 0;
}
if(len > max_size && (copy_size = ((copy_size - write_size) / max_size) * max_size)) {
write(str + write_size, copy_size);
write_size += copy_size;
}
copy_size = len - write_size;
memcpy(buf, str + write_size, copy_size);
pt = copy_size + 1;
}
}
void putcs(char&& ch, size_t len) noexcept {
if(!len) return;
size_t write_size = max_size - pt;
size_t copy_size = len;
if(copy_size <= write_size) {
memset(buf + pt, ch, copy_size);
pt += copy_size;
check();
} else {
if(pt) {
memset(buf + pt, ch, write_size);
write(buf, max_size);
} else {
write_size = 0;
}
if(len > max_size && (copy_size = (copy_size - write_size) / max_size)) {
memset(buf, ch, max_size - pt);
REP(i, copy_size) write(buf, max_size);
write_size += copy_size * max_size;
}
copy_size = len - write_size;
memset(buf, ch, copy_size);
pt = copy_size + 1;
}
}
#ifndef NO_PRINT
template<bool nonewline = true>
void writespace() noexcept {
if(iscontinued) {
if constexpr(nonewline) putc(wspc);
else putc(endl);
}
iscontinued = nonewline;
}
writer& print(const char& c) noexcept {if(c) {if(c == endl) iscontinued = false; putc(c);} else {iscontinued = false;} return *this;}
template <class T>
# ifdef NO_CONCEPT
std::enable_if_t<std::is_integral_v<T> && (!std::is_same_v<T, char>) && (!std::is_same_v<T, bool>), writer&>
# else
requires integer_class<T> writer&
# endif // NO_CONCEPT
print(T n) noexcept {
constexpr int len = std::numeric_limits<T>::digits10 + 1;
constexpr T ten = T(10);
writespace();
if constexpr(std::is_signed_v<T>) {
if(n < 0) {
putc('-');
n = -n;
} else if(!n) {
putc('0');
return *this;
}
} else {
if(!n) {
putc('0');
return *this;
}
}
char s[len];
size_t i = len;
while(n) {
--i;
s[i] = char(n % ten) + '0';
n /= ten;
}
puts(s + i, len - i);
return *this;
}
template <class T, class U, T m>
writer& print(mod_int<T, U, m> n) noexcept {
return print(static_cast<T>(n));
}
template <class T>
# ifdef NO_CONCEPT
std::enable_if_t<std::is_floating_point_v<T>, writer&>
# else
requires std::floating_point<T> writer&
# endif // NO_CONCEPT
print(T n) noexcept {
constexpr int len = std::numeric_limits<T>::digits10 + 1;
constexpr T ten = T(10);
writespace();
if constexpr(std::is_signed_v<T>) {
if(n < T()) {
putc('-');
n = -n;
} else if(!n) {
putc('0');
return *this;
}
} else {
if(!n) {
putc('0');
return *this;
}
}
char s[len];
int lo = int(std::floor(std::log10(n)));
int i = 0;
while(i < len) {
int a;
n = std::remquo(n, std::pow<T>(ten, lo - i), &a);
if(a < 0) {
a += 10;
--s[i - 1];
}
s[i] = std::move(a) + '0';
++i;
}
if(lo >= 0) {
++lo;
if(lo < len) {
puts(s, lo);
putc('.');
puts(s + lo, len - lo);
} else {
puts(s, len);
lo -= len;
if(lo) putcs('0', lo);
}
} else {
putc('0'),putc('.');
putcs('0', -lo);
puts(s, len);
}
return *this;
}
template <class C>
# ifdef NO_CONCEPT
auto
#else
requires (container_forward<C> && !string_input<C>) writer&
# endif // ! NO_CONCEPT
print(const C& v) noexcept
# ifdef NO_CONCEPT
-> decltype(std::begin(v), std::end(v), *this)
# endif // NO_CONCEPT
{for(const auto& e : v) print(e); return *this;}
template <class T, size_t N>
# ifdef NO_CONCEPT
std::enable_if_t<!std::is_same_v<T, char>, writer&>
# else
requires (!string_input<T[N]>) writer&
# endif // NO_CONCEPT
print(const T (&v)[N]) noexcept {for(const T& e : v) print(e); return *this;}
template <class T>
# ifdef NO_CONCEPT
auto
#else
requires string_input<T> writer&
# endif // NO_CONCEPT
print(const T& s) noexcept
# ifdef NO_CONCEPT
-> decltype(static_cast<const char*>(std::data(s)), static_cast<size_t>(std::size(s)), *this)
# endif // NO_CONCEPT
{
const char* const ptr = std::data(s);
const size_t len = std::size(s);
if(len == 0 || (len == 1 && !(*ptr))) {
iscontinued = false;
return *this;
}
puts(ptr, len);
if(*(ptr + len - 1) == endl) {
iscontinued = false;
}
return *this;
}
template <class T1, class T2>
writer& print(std::pair<T1, T2>&& p) noexcept {
print(std::forward<T1>(p.first)), print(std::forward<T2>(p.second));
return *this;
}
template <class... Args>
writer& print(std::tuple<Args...>&& t) noexcept {
return std::apply(print, std::forward<std::tuple<Args...>>(t));
}
template <class... Args>
# ifdef NO_CONCEPT
std::enable_if_t<sizeof...(Args) != 1, writer&>
# else
requires noonly_one<Args...> writer&
# endif // NO_CONCEPT
print(Args&&... args) noexcept {(void)swallow{(print(std::forward<Args>(args)), 0)...}; return *this;}
template <class... Args>
writer& println(Args&&... args) noexcept {writespace<false>(); print(std::forward<Args>(args)...); writespace<false>(); return *this;}
#endif // ! NO_PRINT
};
#ifndef UNSET_STDOUT
writer wt(1);
# ifndef NO_PRINT
template <class... Args> writer& print(Args&&... args) noexcept {return wt.print(std::forward<Args>(args)...);}
template <class... Args> writer& println(Args&&... args) noexcept {return wt.println(std::forward<Args>(args)...);}
# endif // ! NO_PRINT
# ifndef NDEBUG
writer errwt(2);
# ifndef NO_PRINT
template <class... Args> void dprint(Args&&... args) noexcept {errwt.print(std::forward<Args>(args)...).flush();}
template <class... Args> void dprintln(Args&&... args) noexcept {errwt.println(std::forward<Args>(args)...).flush();}
# endif // ! NO_PRINT
# else
# ifndef NO_PRINT
template <class... Args> void dprint(Args&&...) noexcept {}
template <class... Args> void dprintln(Args&&...) noexcept {}
# endif // ! NO_PRINT
# endif // ! NDEBUG
#endif // ! UNSET_STDOUT
} // namespace nlib
#include <numeric>
#include <cmath>
namespace nlib {
#ifndef NO_CONCEPT
template <class T> concept lessthan = requires(const T a, const T b) {
a < b;
};
#endif // ! NO_CONCEPT
template <class T>
#ifndef NO_CONCEPT
requires std::unsigned_integral<T>
#endif // ! NO_CONCEPT
constexpr T combination(T, T);
template <class T>
#ifndef NO_CONCEPT
requires lessthan<T>
#endif // ! NO_CONCEPT
constexpr T& chmin(T& a, const T& b) {if(b < a) a = b; return a;}
template <class T, class Compare>
#ifndef NO_CONCEPT
requires std::predicate<Compare, const T&, const T&>
#endif // ! NO_CONCEPT
constexpr T& chmin(T& a, const T& b, Compare comp) {if(comp(b, a)) a = b; return a;}
template <class T>
#ifndef NO_CONCEPT
requires lessthan<T>
#endif // ! NO_CONCEPT
constexpr T& chmax(T& a, const T& b) {if(a < b) a = b; return a;}
template <class T, class Compare>
#ifndef NO_CONCEPT
requires std::predicate<Compare, const T&, const T&>
#endif // ! NO_CONCEPT
constexpr T& chmax(T& a, const T& b, Compare comp) {if(comp(a, b)) a = b; return a;}
template <class T>
#ifndef NO_CONCEPT
requires lessthan<T>
#endif // ! NO_CONCEPT
constexpr void chminmax(T& a, T& b) {if(b < a) std::swap(a, b);}
template <class T, class Compare>
#ifndef NO_CONCEPT
requires std::predicate<Compare, const T&, const T&>
#endif // ! NO_CONCEPT
constexpr void chminmax(T& a, T& b, Compare comp) {if(comp(b, a)) std::swap(a, b);}
template <class T>
class pow_preproc {
using array_t = T[std::numeric_limits<T>::digits];
array_t _dp = {};
public:
const T base;
constexpr pow_preproc(T b) : base(b) {
_dp[0] = b;
FOR(i, 1, std::numeric_limits<T>::digits) {
_dp[i] = _dp[i - 1] * _dp[i - 1];
}
}
constexpr T operator[](int x) {
return x ? _dp[x - 1] : 1;
}
constexpr T get_pow(T x) {
if(x < 0) return 0;
T y = 1;
for(int i = 0; x; ++i) {
if(x % 2) y *= _dp[i];
x >>= 1;
}
return y;
}
};
template <class T, class U, T m, T max>
class fact_preproc {
public:
using value_type = mod_int<T, U, m>;
static constexpr value_type max_value = max;
private:
mod_int<T, U, m> fact[max], inv[max], finv[max];
public:
};
template <class T>
#ifndef NO_CONCEPT
requires std::integral<T>
#endif // ! NO_CONCEPT
constexpr T combination(T n, T r) {
chmin(r, n - r);
if(r < 0 || n < 0) return 0;
T x = 1, i = 0;
while(i < r) x *= (n - i) / (++i);
return x;
}
template <class T, class U, T m>
constexpr mod_int<T, U, m> combination(mod_int<T, U, m> n, mod_int<T, U, m> r) {
chmin(r, n - r);
mod_int<T, U, m> a = 1, d = 1, i = 0;
while(i < r) {
a *= n - i;
d *= ++i;
}
return a / d;
}
template <size_t s, class T = ull>
struct bits {
using value_type = T;
static constexpr size_t unit_bytes = sizeof(value_type);
static constexpr size_t unit_bits = unit_bytes * 8;
static constexpr size_t length = s / unit_bits + (s % unit_bits != 0);
static constexpr value_type bitmask(size_t id) {return value_type(1) << (id % unit_bits);}
class reference {
friend class bits;
friend class iterator;
value_type* const _ptr;
const value_type _mask;
constexpr reference(value_type* ptr, value_type mask) : _ptr(ptr), _mask(mask) {};
public:
explicit constexpr operator bool() const noexcept {return bool(*_ptr & _mask);}
constexpr bool operator!() const noexcept {return !bool(*this);}
constexpr reference& operator=(bool b) & noexcept {
if(b) set();
else reset();
return *this;
}
constexpr reference& operator=(const reference& b) & noexcept {
return *this = bool(b);
}
constexpr void set() noexcept {*_ptr |= _mask;}
constexpr void reset() noexcept {*_ptr &= ~_mask;}
constexpr void flip() noexcept {*this = !(*this);}
};
class const_reference {
friend class bits;
friend class iterator;
const value_type* const _ptr;
const value_type _mask;
constexpr const_reference(const value_type* ptr, value_type mask) : _ptr(ptr), _mask(mask) {};
public:
explicit constexpr operator bool() const noexcept {return bool(*_ptr & _mask);}
constexpr bool operator!() const noexcept {return !bool(*this);}
constexpr const_reference& operator=(const reference& b) & = delete;
};
class iterator {
friend class bits;
friend class reference;
value_type* _ptr;
size_t _bit;
constexpr iterator(value_type* ptr, size_t bit) : _ptr(ptr), _bit(bit) {};
public:
constexpr iterator& operator++() {
if(++_bit == unit_bits) {
_bit = 0;
++_ptr;
}
return *this;
}
constexpr iterator operator++(int) {iterator i(*this); ++(*this); return i;}
constexpr iterator& operator--() {
if(!_bit) {
_bit = unit_bits;
--_ptr;
}
--_bit;
return *this;
}
constexpr iterator operator--(int) {iterator i(*this); --(*this); return i;}
constexpr reference operator*() const {return reference(_ptr, value_type(1) << _bit);}
};
class const_iterator {
friend class bits;
friend class reference;
const value_type* _ptr;
size_t _bit;
constexpr const_iterator(const value_type* ptr, size_t bit) : _ptr(ptr), _bit(bit) {};
public:
constexpr const_iterator& operator++() {
if(++_bit == unit_bits) {
_bit = 0;
++_ptr;
}
return *this;
}
constexpr const_iterator operator++(int) {iterator i(*this); ++(*this); return i;}
constexpr const_iterator& operator--() {
if(!_bit) {
_bit = unit_bits;
--_ptr;
}
--_bit;
return *this;
}
constexpr const_iterator operator--(int) {iterator i(*this); --(*this); return i;}
constexpr const_reference operator*() const {return const_reference(_ptr, value_type(1) << _bit);}
};
value_type data[length];
constexpr void set() noexcept {constexpr_fill(std::data(data), length, ~value_type());}
constexpr void set(size_t id) noexcept {data[id / unit_bits] |= bitmask(id);}
constexpr void reset() noexcept {constexpr_fill(std::data(data), length, value_type());}
constexpr void reset(size_t id) noexcept {data[id / unit_bits] &= ~bitmask(id);}
constexpr void set(size_t id, bool b) noexcept {if(b) set(id); else reset(id);}
constexpr bool get(size_t id) const noexcept {return bool(data[id / unit_bits] & bitmask(id));}
constexpr void flip() noexcept {REP(i, length) data[i] = ~data[i];}
constexpr bool operator[](size_t id) const noexcept {return get(id);}
constexpr reference operator[](size_t id) noexcept {return reference(data + id / unit_bits, bitmask(id));}
constexpr size_t size() const noexcept {return s;}
constexpr iterator begin() noexcept {return iterator(data, 0);}
constexpr const_iterator begin() const noexcept {return const_iterator(data, 0);}
constexpr iterator end() noexcept {return iterator(data + size() / unit_bits, size() % unit_bits);}
constexpr const_iterator end() const noexcept {return const_iterator(data + size() / unit_bits, size() % unit_bits);}
constexpr const_iterator cbegin() const noexcept {return const_iterator(data, 0);}
constexpr const_iterator cend() const noexcept {return const_iterator(data + size() / unit_bits, size() % unit_bits);}
};
} // namespace nlib
using namespace nlib;
template<class T = ll, class U = double>
T root(T a, T x) {
T y = std::floor(std::pow(U(x), 1./U(a)));
T pow_v = pow_preproc<T>(y).get_pow(a);
dprint(pow_v);
if(pow_v == x) {
return y;
} else if(pow_v < x) {
do {
++y;
pow_v = pow_preproc<T>(y).get_pow(a);
} while(pow_v < x);
--y;
return y;
} else {
do {
--y;
pow_v = pow_preproc<T>(y).get_pow(a);
} while(pow_v > x);
return y;
}
}
int main() {
ll n, i, j = 1, k;
scan(n);
ll count = n + 1;
for(;j < 60; ++j) {
dprint(j);
i = root(j, n);
ll ipow = pow_preproc<ll>(i).get_pow(j);
k = n - ipow;
chmin(count, i + j + k);
}
println(count);
}