#include using namespace std; /*/ #include using namespace atcoder; #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #pragma GCC target("avx,avx2,fma") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") //*/ #define rep(i,n) for(int i=0;i; using ll = long long; using ull = unsigned long long; //*/ template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } typedef pair pii; typedef pair pll; typedef vector vll; typedef vector vint; random_device rnd; mt19937 rng(rnd()); //ミラー・ラビンテスト //nachia さんのやつを窃盗 //nachia::IsPrimeで素数判定 //nachia::Factorizeで素因数分解した結果を出せる //計算量O(N^(1/4)) namespace nachia{ bool IsPrime(unsigned long long x) noexcept { if(x <= 1) return false; if(x % 2 == 0) return x == 2; using u64 = unsigned long long; using u128 = __uint128_t; u64 d = x-1; int s = 0; int q = 63; while(!(d&1)){ d >>= 1; s++; } while(!(d >> q)) q--; u64 r = x; for(int t=0; t<6; t++) r*=2-r*x; u128 n2 = -(u128)x % x; auto red = [=](u128 t) noexcept -> u64 { t = (t + (u128)((u64)t*-r)*x) >> 64; return (t >= x) ? t-x : t; }; u64 one = red(n2); for(u64 base : { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 }){ if(base%x==0) continue; u64 a = base = red(base%x*n2); for(int e=q-1; e>=0; e--){ a = red((u128)a*a); if((d>>e)&1) a = red((u128)a*base); } if(a == one) continue; for(int t=1; t #include namespace nachia{ int Popcount(unsigned long long c) noexcept { #ifdef __GNUC__ return __builtin_popcountll(c); #else c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3)); c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5)); c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17)); c = (c * (~0ull/257)) >> 56; return c; #endif } // please ensure x != 0 int MsbIndex(unsigned long long x) noexcept { #ifdef __GNUC__ return 63 - __builtin_clzll(x); #else int res = 0; for(int d=32; d>=0; d>>=1) if(x >> d){ res |= d; x >>= d; } return res; #endif } // please ensure x != 0 int LsbIndex(unsigned long long x) noexcept { #ifdef __GNUC__ return __builtin_ctzll(x); #else return msb_idx(x & -x); #endif } } #line 5 "nachia\\math\\factorize.hpp" #include namespace nachia{ std::vector> Factorize(unsigned long long x){ if(x == 1) return {}; if(IsPrime(x)) return {{x,1}}; using u64 = unsigned long long; using u128 = __uint128_t; u64 X = x; std::vector p; for(u64 i=2; i<100; i+=1+i%2) if(x%i==0){ p.push_back(i); while(x%i==0) x/=i; } u64 r=1; u128 n2=1; auto updX = [&](){ r = x; for(int t=0; t<6; t++) r*=2-r*x; n2 = -(u128)x % x; }; auto red = [&](u128 t) noexcept -> u64 { t = (t + (u128)((u64)t*-r)*x) >> 64; return (t >= x) ? t-x : t; }; auto mult = [&](u64 a, u64 b) noexcept { return red((u128)red((u128)a*n2)*b); }; auto f = [&](u64 a) noexcept -> u64 { return red((u128)a*a+1); }; auto gcd = [](u64 a, u64 b) noexcept { if(!a || !b) return a|b; int q = LsbIndex(a|b); b >>= LsbIndex(b); a >>= LsbIndex(a); while(a!=b){ if(a>=LsbIndex(b); } else{ a-=b; a>>=LsbIndex(a); } } return a<>7; v^=v<<17; // Xorshift https://www.jstatsoft.org/article/download/v008i14/916 u64 a = v%x, b = f(a); u64 buf = a, sz = 1, nx = 10; while(true){ while(nx != sz && a != b){ buf = mult(buf, a<=b?b-a:a-b); sz++; a = f(a); b = f(f(b)); } u64 g = gcd(buf, x); if(g != 1){ while(p[pi] % g == 0) p[pi] /= g; p.push_back(g); break; } if(a == b) break; nx = sz * 3 / 2; } } } std::vector> res; for(u64 q : p) if(q != 1){ int e=0; while(X%q == 0){ e++; X/=q; } if(e) res.push_back({ q, e }); } return res; } unsigned long long Totient(unsigned long long x){ auto F = Factorize(x); for(auto f : F) x -= x / f.first; return x; } } void solve(){ const int N = 100,K = 100; vector> p(N + 1, vector(K + 1, 0)); p[0][0] = 1; for (long long n = 1; n < N + 1; n++) { for (long long k = 1; k < K + 1; k++) { if (n - k >= 0) { p[n][k] = (p[n - 1][k - 1] + p[n - k][k]); } else { p[n][k] = p[n - 1][k - 1]; } } } ull n; cin >> n; auto pp = nachia::Factorize(n); ll ans = 1; for(auto ps : pp){ int now = 0; for(int i = 1;i <= ps.second;i++)now += p[ps.second][i]; ans *=now; } cout << ans << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; //cin >> t; rep(testcase,t) solve(); }