はまやんはまやんはまやん

hamayanhamayan's blog

約数の総和 [yukicoder 888]

https://yukicoder.me/problems/no/888

前提知識

解説

https://yukicoder.me/submissions/381998

約数列挙は O(sqrt(N))で行うことができる。
これをしていれば答えることができる問題。
やり方はここの約数列挙 O(sqrt(N))に概略がある。
制約が1012の場合は、計算量が O(sqrt(N))であるアルゴリズムを疑おう。

ll N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    auto ed = enumdiv(N);
    ll ans = 0;
    fore(x, ed) ans += x;
    cout << ans << endl;
}