#include #include #define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++) using namespace atcoder; using namespace std; typedef long long ll; vector getDivisors(ll n) { auto mod_mul = [](ll a, ll b, ll mod) -> ll { return (__int128)a * b % mod; }; auto mod_pow = [&](ll base, ll exp, ll mod) -> ll { ll result = 1; base %= mod; while (exp) { if (exp & 1) result = mod_mul(result, base, mod); base = mod_mul(base, base, mod); exp >>= 1; } return result; }; auto is_prime = [&](ll num) -> bool { if (num < 2) return false; int smallPrimes[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}; for (int p : smallPrimes) { if (num == p) return true; if (num % p == 0) return false; } ll d = num - 1; int s = 0; while ((d & 1) == 0) { d /= 2; s++; } ll testPrimes[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; for (ll a : testPrimes) { if (a % num == 0) continue; ll x = mod_pow(a, d, num); if (x == 1 || x == num - 1) continue; bool composite = true; for (int i = 0; i < s - 1; i++) { x = mod_mul(x, x, num); if (x == num - 1) { composite = false; break; } } if (composite) return false; } return true; }; function pollard_rho; pollard_rho = [&](ll num) -> ll { if (num % 2 == 0) return 2; mt19937_64 rng(random_device{}()); uniform_int_distribution dist(2, num - 2); ll x = dist(rng), y = x, c = dist(rng), d = 1; auto f = [&](ll x, ll c, ll mod) -> ll { return (mod_mul(x, x, mod) + c) % mod; }; while (d == 1) { x = f(x, c, num); y = f(y, c, num); y = f(y, c, num); d = gcd(abs(x - y), num); if (d == num) return pollard_rho(num); } return d; }; function &)> factorize; factorize = [&](ll num, vector &factors) { if (num == 1) return; if (is_prime(num)) { factors.push_back(num); return; } ll factor = pollard_rho(num); factorize(factor, factors); factorize(num / factor, factors); }; vector factors; factorize(n, factors); sort(factors.begin(), factors.end()); vector> factorCounts; for (ll f : factors) { if (factorCounts.empty() || factorCounts.back().first != f) factorCounts.push_back({f, 1}); else factorCounts.back().second++; } vector divisors; function dfs = [&](int idx, ll current) { if (idx == factorCounts.size()) { divisors.push_back(current); return; } ll prime = factorCounts[idx].first; int exp = factorCounts[idx].second; for (int i = 0; i <= exp; i++) { dfs(idx + 1, current); current *= prime; } }; dfs(0, 1); sort(divisors.begin(), divisors.end()); return divisors; } int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); ll n; cin >> n; vector divisors = getDivisors(n); ll ans = 0; for (ll d : divisors) { ans += d; } cout << ans << endl; }