// SPDX-License-Identifier: MIT // (c) 2023 TwoSquirrels // my AtCoder environment: https://github.com/TwoSquirrels/atcoder-env //#define DEBUG // enable debug mode when compiled with -DDEBUG #ifdef DEBUG # define IS_DEBUG (1) #else // QCFium method //# pragma GCC target("avx2") # pragma GCC optimize("O3") # pragma GCC optimize("unroll-loops") //# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") # define IS_DEBUG (0) #endif /// includes // standard libraries #if __has_include() # include #else // // C++17 (clang) # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include #endif // /// abi #if __has_include() # define INCLUDED_CXXABI # include #endif // // boost libraries #if __has_include() # define INCLUDED_BOOST_CPP_INT # include #endif #if __has_include() # define INCLUDED_BOOST_PRIME # include #endif #if __has_include() # define INCLUDED_BOOST_MILLER_RABIN # include #endif // atcoder libraries #if __has_include() # define INCLUDED_ACL # include #endif /// sfinae // is_pair template inline constexpr bool is_pair_v = false; template inline constexpr bool is_pair_v> = true; // is_tuple template inline constexpr bool is_tuple_v = false; template inline constexpr bool is_tuple_v> = true; // istreamable #if __cplusplus >= 202002L template concept istreamable_v = requires (T a) { std::cin >> a; }; #else // C++20 template inline constexpr bool istreamable_v = false; template inline constexpr bool istreamable_v> std::declval())>> = true; #endif // C++20 // ostreamable #if __cplusplus >= 202002L template concept ostreamable_v = requires (T a) { std::cout << a; }; #else // C++20 template inline constexpr bool ostreamable_v = false; template inline constexpr bool ostreamable_v())>> = true; #endif // C++20 // iterable #if __cplusplus >= 202002L # if __has_include() template concept iterable_v = std::ranges::range; # else // template concept iterable_v = requires (T a) { std::begin(a); std::end(a); }; # endif // C++20 #else // C++20 template inline constexpr bool iterable_v = std::is_same_v())), decltype(std::end(std::declval()))>; #endif // C++20 /// utils template inline std::string get_typename(std::size_t length_limit = std::string::npos) { std::string name; #ifdef INCLUDED_CXXABI name = abi::__cxa_demangle(typeid(T).name(), nullptr, nullptr, nullptr); #else // INCLUDED_CXXABI name = typeid(T).name(); #endif // INCLUDED_CXXABI #ifdef __ANDROID__ name = std::regex_replace(name, std::regex("::__ndk1::"), "::"); #endif // __ANDROID__ if (name.length() > length_limit) name = name.substr(0, length_limit - 3) + "..."; return name; } template constexpr T inf() { if constexpr (std::numeric_limits::has_infinity) return std::numeric_limits::infinity(); return std::numeric_limits::max() / 2.125L; } template constexpr int sin90(T theta90) { if (theta90 % 2 == 0) return 0; return (theta90 % 4 + 4) % 4 < 2 ? 1 : -1; } template constexpr int cos90(T theta90) { return sin90(theta90 + 1); } template constexpr int sin45(T theta45) { if (theta45 % 4 == 0) return 0; return (theta45 % 8 + 8) % 8 < 4 ? 1 : -1; } template constexpr int cos45(T theta45) { return sin45(theta45 + 2); } template inline bool chmin(T &&a, const U b) { const bool compare = a > b; if (compare) a = b; return compare; } template inline bool chmax(T &&a, const U b) { const bool compare = a < b; if (compare) a = b; return compare; } long long powi(int base, int exponent = 2) { long long ans = 1; for (int i = exponent; i != 0; i += (i >= 0 ? -1 : 1)) { if (i >= 0) ans *= base; else ans /= base; if (ans == 0) break; } return ans; } #ifdef INCLUDED_ACL template T mint_inv(T x) { constexpr int memo_limit = 1 << 24; static std::array memo; if (x.val() >= memo_limit) return x.inv(); if (memo[x.val()] == 0) memo[x.val()] = x.inv(); return memo[x.val()]; } #endif // INCLUDED_ACL template bool is_prime(T n) { if (n <= 1) return false; if (n == 2 || n == 3) return true; if (n % 2 == 0 || n % 3 == 0) return false; // miller rabin #ifdef INCLUDED_ACL if (n <= std::min(1LL << 32, static_cast(std::numeric_limits::max()))) { return atcoder::internal::is_prime_constexpr(n); } #endif // INCLUDED_ACL #ifdef INCLUDED_BOOST_MILLER_RABIN return boost::multiprecision::miller_rabin_test(n, 25); #endif // INCLUDED_BOOST_MILLER_RABIN // binary search #ifdef INCLUDED_BOOST_PRIME if (n <= boost::math::prime(boost::math::max_prime)) { int left = 0, right = boost::math::max_prime + 1; while (right - left > 1) { auto mid = (left + right) / 2; (boost::math::prime(mid) <= n ? left : right) = mid; } return n == boost::math::prime(left); } #endif // INCLUDED_BOOST_PRIME // trial T tried = 3; #ifdef INCLUDED_BOOST_PRIME for (int i = 2; i <= int(boost::math::max_prime); i++) { const auto prime_i = boost::math::prime(i); if (prime_i > n / prime_i) return true; if (n % prime_i == 0) return false; tried = prime_i; } #endif // INCLUDED_BOOST_PRIME for (T i = (tried + 5) / 6 * 6; (i - 1) * (i - 1) <= n; i += 6) { if (n % (i - 1) == 0 || n % (i + 1) == 0) return false; } return true; } // thanks to https://perogram.hateblo.jp/entry/2019/03/29/193632 template std::vector> factors(T n) { constexpr int spf_limit = 1 << 24; std::vector> result; if (n < 0) { result.emplace_back(-1, 1); const auto natural = factors(-n); result.insert(result.end(), natural.begin(), natural.end()); } else if (n == 0) result.emplace_back(0, 1); else if (n == 1); else if (osa_k && n < spf_limit) { static std::array spf; if (spf[0] == 0) { for (int i = 0; i < spf_limit; i++) spf[i] = i % 2 == 0 ? 2 : i % 3 == 0 ? 3 : i; spf[0] = 1; for (int p1 = 6; (p1 - 1) * (p1 - 1) <= spf_limit; p1 += 6) { if (spf[p1 - 1] == p1 - 1) for (int i = p1 - 1; i < spf_limit; i += p1 - 1) if (spf[i] == i) spf[i] = p1 - 1; if (spf[p1 + 1] == p1 + 1) for (int i = p1 + 1; i < spf_limit; i += p1 + 1) if (spf[i] == i) spf[i] = p1 + 1; } } while (n != 1) { if (!result.empty() && result.back().first == spf[n]) result.back().second++; else result.emplace_back(spf[n], 1); n /= spf[n]; } } else { int expo = 0; while (n % 2 == 0) { n /= 2; expo++; } if (expo != 0) result.emplace_back(2, expo); expo = 0; while (n % 3 == 0) { n /= 3; expo++; } if (expo != 0) result.emplace_back(3, expo); T tried = 3; #ifdef INCLUDED_BOOST_PRIME for (int i = 2; i <= int(boost::math::max_prime); i++) { const auto prime_i = boost::math::prime(i); if (prime_i > n / prime_i) break; expo = 0; while (n % prime_i == 0) { n /= prime_i; expo++; } result.emplace_back(prime_i, expo); tried = prime_i; } if (osa_k && n < spf_limit) { const auto rest = factors(n); result.insert(result.end(), rest.begin(), rest.end()); n = 1; } #endif // INCLUDED_BOOST_PRIME if (is_prime(n)) { result.emplace_back(n, 1); n = 1; } for (T i = (tried + 5) / 6 * 6; (i - 1) * (i - 1) <= n; i += 6) { expo = 0; while (n % (i - 1) == 0) { n /= (i - 1); expo++; } if (expo != 0) result.emplace_back(i - 1, expo); expo = 0; while (n % (i + 1) == 0) { n /= (i + 1); expo++; } if (expo != 0) result.emplace_back(i + 1, expo); if (osa_k && n < spf_limit) { const auto rest = factors(n); result.insert(result.end(), rest.begin(), rest.end()); n = 1; } } if (n != 1) result.emplace_back(n, 1); } return result; } template std::vector divisors(T n) { std::vector result(1, 1); for (auto [prime, expo] : factors(n)) { const int result_size = result.size(); T pow_i = 1; for (int i = 1; i <= expo; i++) { pow_i *= prime; for (int k = 0; k < result_size; k++) result.emplace_back(result[k] * pow_i); } } std::sort(result.begin(), result.end()); return result; } template T fact(int n, bool inv = false) { assert(n >= 0); static std::vector> factorials = { { 1, 1 } }; for (int i = factorials.size(); i <= n; i++) factorials.emplace_back(i * factorials[i - 1].first, 0); if (inv && factorials[n].second == 0) { if constexpr (std::is_integral_v) factorials[n].second = factorials[n].first <= 1 ? 1 : 0; #ifdef INCLUDED_ACL else if constexpr (atcoder::internal::is_modint::value) factorials[n].second = mint_inv(factorials[n].first); #endif // INCLUDED_ACL else factorials[n].second = 1 / factorials[n].first; } return inv ? factorials[n].second : factorials[n].first; } template T perm(int n, int k) { return fact(n) * fact(n - k, true); } template T comb(int n, int k) { return perm(n, k) * fact(k, true); } // TODO: compressor /*template struct compressor { std::vector positions; compressor() = default; compressor(const std::vector &initial_pos) { } };*/ template std::vector> rotate(std::vector> grid, int angle = 1) { angle %= 4; if (angle == 0) return grid; auto h = grid.size(), w = grid[0].size(); auto rotated = std::vector(w, std::vector(h)); for (int y = 0; y < h; y++) for (int x = 0; x < w; x++) rotated[w - 1 - x][y] = grid[y][x]; return rotate(rotated, angle - 1); } std::string int128_to_str(__int128_t target) { std::string target_str; __uint128_t target_tmp = target < 0 ? -target : target; do { target_str += '0' + target_tmp % 10; target_tmp /= 10; } while (target_tmp != 0); if (target < 0) target_str += '-'; std::reverse(target_str.begin(), target_str.end()); return target_str; } template std::string to_pretty_str(T target) { using namespace std; string str; if constexpr (is_void_v) str += "void"s; else if constexpr (is_null_pointer_v) str += "null"s; else if constexpr (is_same_v) str += target ? "true"s : "false"s; else if constexpr (is_same_v || is_same_v || is_same_v || is_same_v) { str += "'"s + target + "'"s; #ifdef INCLUDED_ACL } else if constexpr (atcoder::internal::is_modint::value) { str += to_string(target.val()) + "(mod)"s; #endif // INCLUDED_ACL } else if constexpr (is_arithmetic_v) { if constexpr (is_same_v) str += int128_to_str(target); else str += to_string(target); if constexpr (is_unsigned_v) str += "u"s; if constexpr (is_same_v, long>) str += "L"s; else if constexpr (is_same_v, long long>) str += "LL"s; else if constexpr (is_same_v) str += "LLL"s; } else if constexpr (is_pair_v) { str += "("s + to_pretty_str(target.first); str += ", "s + to_pretty_str(target.second) + ")"s; } else if constexpr (is_convertible_v) { str += "\""s + target + "\""s; } else if constexpr (is_array_v) { str += "["s; bool separate = false; for (const auto &target_i : target) { if (separate) str += ", "s; str += to_pretty_str(target_i); separate = true; } str += "]"s; } else if constexpr (iterable_v) { str += get_typename(20) + "{"s; bool separate = false; for (const auto &target_i : target) { if (separate) str += ","s; str += " "s + to_pretty_str(target_i); separate = true; } if (separate) str += " "s; str += "}"s; } else { str += "<"s + get_typename(20); str += " ("s + to_string(sizeof(target)) + " byte)>"s; } return str; } // input #ifdef DEBUG std::chrono::milliseconds input_total_ms{0}; #endif // DEBUG template inline void read_stdin(T &&target) { #ifdef DEBUG using namespace std::chrono; const auto start = system_clock::now(); std::cin >> target; const auto end = system_clock::now(); input_total_ms += duration_cast(end - start); #else // DEBUG std::cin >> target; #endif // DEBUG } template inline T input(T &&target) { using T_V = std::remove_reference_t; if constexpr (istreamable_v) read_stdin(target); else if constexpr (iterable_v) for (auto &&target_i : target) input(target_i); else if constexpr (is_pair_v) { input(target.first); input(target.second); } else if constexpr (std::is_convertible_v) { long long n; target = input(n); } else { #ifdef DEBUG std::cerr << "[WARN] Type " << get_typename() << " is invalid, so input is skipped;" << std::endl; #endif //DEBUG } return target; } // input and initialize struct Scanner { template inline operator T() const { T target; return input(target); } } scan; // output template inline void write_stdout(T target, bool flush = false) { std::cout << target; if (flush) std::cout << std::flush; } template inline void output(T target, Sep separator = ' ', bool flush = false) { if constexpr (ostreamable_v) { write_stdout(target, flush); } else if constexpr (std::is_convertible::value) { write_stdout(int128_to_str(target), flush); # ifdef INCLUDED_ACL } else if constexpr (atcoder::internal::is_modint::value) { output(target.val(), separator, flush); # endif // INCLUDED_ACL } else if constexpr (iterable_v) { bool separate = false; for (const auto target_i : target) { if (separate) write_stdout(separator); output(target_i, separator); separate = true; } if (flush) write_stdout("", flush); } else if constexpr (is_pair_v) { output(target.first, separator); write_stdout(separator); output(target.second, separator, flush); } else { write_stdout("", flush); } } template inline void outputln(T target, Sep separator = ' ', bool flush = false) { output(target, separator); write_stdout('\n', flush); } // debug output #ifdef DEBUG std::chrono::milliseconds debug_total_ms{0}; template void debug_txt_f(F callback, int line = -1, std::string file = (__FILE__)) { using namespace std::chrono; const auto start = system_clock::now(); std::string dump_str = "[DEBUG] "; if (line >= 0) { dump_str += "("; if (file != (__FILE__)) dump_str += file + ":"; dump_str += "L" + std::to_string(line) + ") "; } dump_str += callback(); std::cerr << dump_str << std::endl; const auto end = system_clock::now(); debug_total_ms += duration_cast(end - start); } # define debug_txt(txt) (debug_txt_f([]() { return to_pretty_str(txt); }, (__LINE__), (__FILE__)), true) template void dump_f(std::string labels, std::tuple targets_tupl, int line = -1, std::string file = (__FILE__)) { debug_txt_f([=]() { std::string txt; std::apply([labels, &txt](auto... targets) { int i = 0, label_left = 0; (([&](auto target) { const auto label_len = labels.find(',', label_left) - label_left; const auto label = std::regex_replace(labels.substr(label_left, label_len), std::regex("^\\s+|\\s+$"), ""); if (i >= 1) txt += ", "; txt += label + ": " + to_pretty_str(target); label_left += label_len + 1; i++; })(targets), ...); txt += ";"; }, targets_tupl); return txt; }, line, file); } # define dump(...) (dump_f((#__VA_ARGS__), std::make_tuple(__VA_ARGS__), (__LINE__), (__FILE__)), true) void dump_canvas_f(std::string label, std::vector canvas, int line = -1, std::string file = (__FILE__)) { debug_txt_f([=]() { int h = canvas.size(), w = canvas[0].size(); std::string txt = label + " (" + std::to_string(h) + " x " + std::to_string(w) + ")\n"; std::string ruler0(w, ' '), ruler1(w, '-'); for (int x = 0; x < w; x += 4) { auto x_s = std::to_string(x); for (std::size_t i = 0; i < x_s.size(); i++) ruler0[x - i] = x_s[x_s.size() - i - 1]; ruler1[x] = '+'; } txt += " |" + ruler0 + "\n---+" + ruler1; for (int y = 0; y < h; y++) { std::string ruler = " |"; if (y % 4 == 0) { auto y_s = std::to_string(y); for (std::size_t i = 0; i < y_s.size(); i++) ruler[2 - i] = y_s[y_s.size() - i - 1]; ruler[3] = '+'; } txt += "\n" + ruler + canvas[y]; } return txt; }, line, file); } # define dump_canvas(canvas) (dump_canvas_f((#canvas), (canvas), (__LINE__), (__FILE__)), true) // TODO: dump_table #else // DEBUG # pragma GCC diagnostic push # pragma GCC diagnostic ignored "-Wunused-value" # define debug_txt(...) (false) # define dump(...) (false) # define dump_canvas(...) (false) # pragma GCC diagnostic pop #endif // DEBUG /// main #if !defined(__INCLUDE_LEVEL__) || __INCLUDE_LEVEL__ <= 1 inline std::string cp_main(); int main() { using namespace std; # ifdef DEBUG using namespace std::chrono; cerr << "[INFO] running in debug mode!" << endl; const auto start = system_clock::now(); try { # endif // DEBUG cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(8); // run!!! const auto result = cp_main(); if (!result.empty()) write_stdout(result); # ifdef DEBUG write_stdout('\n', true); } catch (exception &e) { write_stdout('\n', true); cerr << "[ERROR] " << e.what() << endl; } const auto end = system_clock::now(); const auto time_ms = duration_cast(end - start) - input_total_ms - debug_total_ms; cerr << "[INFO] finished in " << time_ms.count() << " ms!" << endl; # endif // DEBUG return 0; } #endif // __INCLUDE_LEVEL__ /// aliases using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; using i128 = __int128; using u128 = unsigned __int128; using f32 = float; using f64 = double; using f128 = long double; using str = std::string; template using vec = std::vector; template > using p_que = std::priority_queue, Compare>; template > using mset = std::multiset; template > using mmap = std::multimap; template using u_set = std::unordered_set; template using u_mset = std::unordered_multiset; template using u_map = std::unordered_map; template using u_mmap = std::unordered_multimap; #ifdef INCLUDED_BOOST_CPP_INT using bigint = boost::multiprecision::cpp_int; #endif // INCLUDED_BOOST_CPP_INT using namespace std; #if __cplusplus >= 202002L && __has_include() namespace rng = std::ranges; namespace viw = std::ranges::views; #endif // C++20 && #ifdef INCLUDED_ACL using namespace atcoder; #endif // INCLUDED_ACL #pragma GCC diagnostic push # pragma GCC diagnostic ignored "-Wunused-variable" constexpr auto infi = inf(); constexpr auto infl = inf(); constexpr auto infd = inf(); constexpr auto infld = inf(); const std::array YN = { "No"s, "Yes"s }; const std::array AB = { "Bob"s, "Alice"s }; const std::array FS = { "Second"s, "First"s }; const std::array TA = { "Aoki"s, "Takahashi"s }; #pragma GCC diagnostic pop // functions #define tostr to_string #define dist distance #define min_e min_element #define max_e max_element #define iota_v iota_view #define p1 first #define p2 second #define has contains #define eb emplace_back #define ef emplace_front #define pb pop_back #define pf pop_front // cast #define bit_width(x) (int(std::bit_width(x))) // repeat #define reps(i, l, r) for (std::decay_t i##_right = (r), i = (l); i < i##_right; i++) #define rep(i, n) reps(i, 0, n) #define rreps(i, l, r) for (std::decay_t i##_left = (l), i = (r) - 1; i >= i##_left; i--) #define rrep(i, n) rreps(i, 0, n) #define each(for_able) for (auto &&for_able##_i : (for_able)) // iterate #define all(for_able) (std::begin(for_able)), (std::end(for_able)) #define rev(for_able) (std::rbegin(for_able)), (std::rend(for_able)) // lambda #define pred(x, expr) ([&](auto &&x) -> bool { return (expr); }) #define comp(x, y, expr) ([&](auto &&x, auto &&y) -> bool { return (expr); }) /// answer //using mint=modint998244353; inline str cp_main() { i64 n=scan,a=scan,b=scan,c=scan; vec> facts(n+1,{1,false}); reps(i,1,n+1) { facts[i].p1=facts[i-1].p1*i%n; facts[i].p2=facts[i-1].p2||facts[i-1].p1*i>=n; } vec cost(n+1,infl); p_que,greater<>> q; q.emplace(cost[1]=0,1); while(!q.empty()){ auto [x_c,x]=q.top(); q.pop(); if(x_c>(n-1)*a)break; if(x_c>cost[x])continue; dump(x_c,x); if(x=2) { i64 nxt=x; reps(k,2,40) { if(x_c+b*k>(n-1)*a)break; nxt*=x; if(nxt>=n&&chmin(cost[n],x_c+b*k))q.emplace(cost[n],n); nxt%=n; if(chmin(cost[nxt],x_c+b*k)) { if(nxt==0)break; q.emplace(cost[nxt],nxt); } } } if(x>=2) { auto [nxt,nxt_big]=facts[min(x,n)]; if(nxt_big&&chmin(cost[n],x_c+c))q.emplace(cost[n],n); if(chmin(cost[nxt],x_c+c)) { if(nxt==0)break; q.emplace(cost[nxt],nxt); } } } dump(cost); outputln(cost[0]); return ""; }