#include //#include using namespace std; // using namespace atcoder; // using mint = modint1000000007; // const int mod = 1000000007; // using mint = modint998244353; // const int mod = 998244353; // const int INF = 1e9; // const long long LINF = 1e18; #define rep(i, n) for (int i = 0; i < (n); ++i) #define rep2(i, l, r) for (int i = (l); i < (r); ++i) #define rrep(i, n) for (int i = (n)-1; i >= 0; --i) #define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i) #define all(x) (x).begin(), (x).end() #define allR(x) (x).rbegin(), (x).rend() #define P pair template inline bool chmax(A& a, const B& b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(A& a, const B& b) { if (a > b) { a = b; return true; } return false; } /** * @file integer.hpp * @brief 整数型に関する補助機能 * @author kwm_t * @see https://github.com/kwm-t/cp-library/blob/main/base/integer.hpp */ #ifndef KWM_T_BASE_INTEGR_HPP #define KWM_T_BASE_INTEGR_HPP #include /** * @brief ローカル環境用(MSC)int128 */ #ifdef _MSC_VER using int128 = long long; #else using int128 = __int128; std::ostream& operator<<(std::ostream& dest, int128 value) { if (value == 0) { return dest << 0; } if (value < 0) { dest << '-'; value = -value; } char buffer[128]; char* p = end(buffer); while (value > 0) { *--p = '0' + (value % 10); value /= 10; } return dest.write(p, end(buffer) - p); } #endif #endif // KWM_T_BASE_INTEGR_HPP /** * @file miller_rabin.hpp * @brief Miller-Rabin 素数判定法 * @author kwm_t * @see https://github.com/kwm-t/cp-library/blob/main/math/miller_rabin.hpp */ #ifndef KWM_T_MATH_MILLER_RABIN_HPP #define KWM_T_MATH_MILLER_RABIN_HPP #include // #include "base/integer.hpp" namespace kwm_t::math { /** * @brief Miller-Rabin 素数判定(64bit対応・確定的) * * 計算量: * O(log n) * * 制約: * - n < 2^64 * * verified: * https://judge.yosupo.jp/submission/367299 */ struct MillerRabin { private: static int128 modmul(int128 a, int128 b, int128 mod) { return (a * b) % mod; } static long long modpow(long long a, long long e, long long mod) { int128 res = 1; int128 base = a % mod; while (e) { if (e & 1) res = modmul(res, base, mod); base = modmul(base, base, mod); e >>= 1; } return (long long)res; } public: static bool is_prime(long long n) { if (n < 2) return false; // 小さい素数で弾く for (long long p : {2, 3, 5, 7, 11, 13, 17, 19, 23}) { if (n == p) return true; if (n % p == 0 && n != p) return false; } long long d = n - 1; int s = 0; while ((d & 1) == 0) { d >>= 1; ++s; } // 64bitで確定的な基底 static const long long bases[] = { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 }; for (long long a : bases) { if (a % n == 0) continue; long long x = modpow(a, d, n); if (x == 1 || x == n - 1) continue; bool composite = true; for (int r = 1; r < s; ++r) { x = modmul(x, x, n); if (x == n - 1) { composite = false; break; } } if (composite) return false; } return true; } }; } // namespace kwm_t::math #endif // KWM_T_MATH_MILLER_RABIN_HPP /** * @file pollard_rho.hpp * @brief Pollard's rho 法 * @author kwm_t * @see https://github.com/kwm-t/cp-library/blob/main/math/pollard_rho.hpp */ #ifndef KWM_T_MATH_POLLARD_RHO_HPP #define KWM_T_MATH_POLLARD_RHO_HPP #include #include #include #include // #include "base/integer.hpp" // #include "miller_rabin.hpp" namespace kwm_t::math { /** * @brief Pollard Rho による素因数分解(64bit対応) * * 計算量: * 平均 O(n^{1/4}) * * 制約: * - n < 2^64 * * verified: * https://judge.yosupo.jp/submission/367301 */ struct PollardRho { private: std::mt19937_64 rng; static int128 modmul(int128 a, int128 b, int128 mod) { return (a * b) % mod; } static long long f(long long x, long long c, long long mod) { return (modmul(x, x, mod) + c) % mod; } long long pollard(long long n) { if (n % 2 == 0) return 2; std::uniform_int_distribution dist(2, n - 2); while (true) { long long x = dist(rng); long long y = x; long long c = dist(rng); long long d = 1; while (d == 1) { x = f(x, c, n); y = f(f(y, c, n), c, n); long long diff = x > y ? x - y : y - x; d = std::gcd(diff, n); } if (d != n) return d; } } void factor_rec(long long n, std::vector& res) { if (n == 1) return; if (MillerRabin::is_prime(n)) { res.push_back(n); return; } long long d = pollard(n); factor_rec(d, res); factor_rec(n / d, res); } public: PollardRho() : rng(std::random_device{}()) {} /** * @brief 素因数分解(非ソート) */ std::vector factor(long long n) { std::vector res; factor_rec(n, res); return res; } }; } // namespace kwm_t::math #endif // KWM_T_MATH_POLLARD_RHO_HPP int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); //Rho rho; long long n; cin >> n; kwm_t::math::PollardRho pr; auto v = pr.factor(n); mapmp; rep(i, v.size()) mp[v[i]]++; long long ans = 1; vector devide = { 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, 6842, 8349, 10143, 12310, 14883, 17977, 21637, 26015, 31185, 37338, 44583, 53174, 63261, 75175, 89134, 105558, 124754, 147273, 173525, 204226, 239943, 281589, 329931, 386155, 451276, 526823, 614154, 715220, 831820 }; for (auto [k, v] : mp) ans *= devide[v]; cout << ans << endl; return 0; return 0; }