//素因数分解による解法も試してみる //こちらもO(sqrt(N))くらい。 #include #include #define int long long using namespace std; int n; signed main() { typedef pair P; vector

pr; cin >> n; for (int i = 2; i * i <= n; i++) { int cnt = 0; while (n % i == 0) { n /= i; cnt++; } if (cnt > 0) pr.push_back(P(i, cnt)); } if (n > 1) pr.push_back(P(n, 1)); int ans = 1; for (int i = 0; i < pr.size(); i++) { int a = pr[i].first; int ssum = 0; int mul = 1; for (int j = 0; j <= pr[i].second; j++) { ssum += mul; mul *= a; } ans *= ssum; } cout << ans << endl; return 0; }