#line 1 "test/yukicoder/888.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/888" #line 2 "template.hpp" // #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include using namespace std; // https://xn--kst.jp/blog/2019/08/29/cpp-comp/ // debug methods // usage: debug(x,y); // vector 出力できるように修正 template ostream& debug_print(ostream& os, const vector& v) { os << "["; for (size_t i = 0; i < v.size(); ++i) { os << v[i]; if (i < v.size() - 1) os << ", "; } os << "]"; return os; } template ostream& debug_print(ostream& os, const T& var) { os << var; return os; } #define CHOOSE(a) CHOOSE2 a #define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x #define debug_1(x1) { cout << #x1 << ": "; debug_print(cout, x1) << endl; } #define debug_2(x1, x2) { cout << #x1 << ": "; debug_print(cout, x1) << ", " << #x2 << ": "; debug_print(cout, x2) << endl; } #define debug_3(x1, x2, x3) { cout << #x1 << ": "; debug_print(cout, x1) << ", " << #x2 << ": "; debug_print(cout, x2) << ", " << #x3 << ": "; debug_print(cout, x3) << endl; } #define debug_4(x1, x2, x3, x4) { cout << #x1 << ": "; debug_print(cout, x1) << ", " << #x2 << ": "; debug_print(cout, x2) << ", " << #x3 << ": "; debug_print(cout, x3) << ", " << #x4 << ": "; debug_print(cout, x4) << endl; } #define debug_5(x1, x2, x3, x4, x5) { cout << #x1 << ": "; debug_print(cout, x1) << ", " << #x2 << ": "; debug_print(cout, x2) << ", " << #x3 << ": "; debug_print(cout, x3) << ", " << #x4 << ": "; debug_print(cout, x4) << ", " << #x5 << ": "; debug_print(cout, x5) << endl; } #ifdef LOCAL #define debug(...) CHOOSE((__VA_ARGS__, debug_5, debug_4, debug_3, debug_2, debug_1, ~))(__VA_ARGS__) #else #define debug(...) #endif using ll = long long; using vl = vector; using Graph = vector>; using P = pair; #define all(v) v.begin(), v.end() template inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); } template inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); } #define rep1(i, n) for(ll i = 1; i <= ((ll)n); ++i) // https://trap.jp/post/1224/ template constexpr auto min(T... a) { return min(initializer_list>{a...}); } template constexpr auto max(T... a) { return max(initializer_list>{a...}); } template void input(T &...a) { (cin >> ... >> a); } template void input(vector &a) { for(T &x : a) cin >> x; } void print() { cout << '\n'; } template void print(const T &a, const Ts &...b) { cout << a; (cout << ... << (cout << ' ', b)); cout << '\n'; } template struct is_container : std::false_type {}; template struct is_container().begin()), decltype(std::declval().end())>> : std::true_type {}; template typename enable_if::value>::type print(const Container& x) { if (!x.empty()) { auto it = x.begin(); for (; it != prev(x.end()); ++it) { cout << *it << " "; } cout << *it << "\n"; // 最後の要素を出力して改行 } } #define INT(...) \ int __VA_ARGS__; \ input(__VA_ARGS__) #define LL(...) \ long long __VA_ARGS__; \ input(__VA_ARGS__) #define STR(...) \ string __VA_ARGS__; \ input(__VA_ARGS__) #define REP1(a) for(ll i = 0; i < a; i++) #define REP2(i, a) for(ll i = 0; i < a; i++) #define REP3(i, a, b) for(ll i = a; i < b; i++) #define REP4(i, a, b, c) for(ll i = a; i < b; i += c) #define overload4(a, b, c, d, e, ...) e #define rep(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__) ll inf = 3e18; vl dx = {1, -1, 0, 0}; vl dy = {0, 0, 1, -1}; #line 3 "math/miller_rabin.hpp" // https://drken1215.hatenablog.com/entry/2023/05/23/233000 // todo モンゴメリ乗算 bool is_prime(ll n) { auto pow_mod = [&n](__int128 a, ll d) { __int128 res = 1; while(d) { if(d & 1) { res *= a; if(res >= n) res %= n; } a *= a; if(a >= n) a %= n; d >>= 1; } return res; }; if(n == 2 or n == 7 or n == 61) { return true; } if(n % 2 == 0 or n == 1) { return false; } ll d = n - 1; ll s = 0; while(d % 2 == 0) { d >>= 1; s++; } auto check = [&](ll a) { ll ad = pow_mod(a, d); if(ad == 1) { return true; } rep(i, s) { if(ad == n - 1) { return true; } if(i < s - 1) ad = pow_mod(ad, 2); } return false; }; if(n < 4759123141) { for(auto a : vl{2, 7, 61}) { if(!check(a)) { return false; } } return true; } else { for(auto a : vl{2, 325, 9375, 28178, 450775, 9780504, 1795265022}) { if(n == a) { return true; } if(!check(a)) { return false; } } return true; } } #line 3 "math/pollard_rho.hpp" // https://manabitimes.jp/math/1192 // https://wacchoz.hatenablog.com/entry/2019/01/05/230128 // https://nyaannyaan.github.io/library/prime/fast-factorize.hpp namespace fast_factorize { ll pollard_rho(ll n) { // nの素因数を1つ返す // 1には1を返す if(n == 1) { return 1; } if(~n & 1) { return 2; } if(is_prime(n)) { return n; } ll r = 1; auto f = [&n, &r](ll m) { return ((__int128)m * m + r) % n; }; ll x = 1, y = f(x); while(1) { ll g = gcd(n, abs(x - y)); if(1 < g and g < n) { return pollard_rho(g); } else if(g == 1) { x = f(x); y = f(f(y)); } else { r = rand() % (n - 2) + 2; x = 1; y = f(x); } } } vl inner_factorize(ll n) { vl res; if(n == 1) { return res; } while(n > 1 and !is_prime(n)) { ll p = pollard_rho(n); while(n % p == 0) { res.push_back(p); n /= p; } } if(n > 1) { res.push_back(n); } return res; } vl factorize(ll n) { auto res = inner_factorize(n); sort(all(res)); return res; } map factor_count(ll n) { auto res = inner_factorize(n); map mp; for(auto &x : res) { mp[x]++; } return mp; } vl divisors(ll n) { vl res = {1}; auto mp = factor_count(n); for(auto [p, cnt] : mp) { ll sz = ssize(res); rep(i, sz) { ll pi = p; rep(_, cnt) { res.push_back(res[i] * pi); pi *= p; } } } sort(all(res)); return res; } } // namespace fast_factorize using fast_factorize::factorize; using fast_factorize::factor_count; using fast_factorize::divisors;; #line 3 "test/yukicoder/888.test.cpp" void solve() { LL(n); auto div = divisors(n); ll ans = accumulate(all(div), 0LL); print(ans); } int main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); ll t = 1; rep(_, t) solve(); }