同類項でまとめると， 調べるべき \(i\) の個数が \(O(2\sqrt{N})\) 個で抑えられるのがポイント．
見積:
ざっくり言えば，\(x := \lfloor \frac{N}{i} \rfloor\) は \(\frac{N}{i}\) とほぼ同じ． よって，\(N\) の約数と同じ程度しか \(x\) の値は出てこないと思われるので， \(O(2\sqrt{N})\) と予想出来る．
実際， \begin{align} && \sum_{i \in [1,N]} \lfloor \frac{N}{i} \rfloor \\ &=& \sum_{i \in [1,\sqrt{N}]} \lfloor \frac{N}{i} \rfloor + \sum_{i \in (\sqrt{N},N]} \lfloor \frac{N}{i} \rfloor \end{align} と分解出来る． \({i \in [1,\sqrt{N}]}\) の部分は，同類項でまとめなくとも \(\sqrt{N}\)個． \({i \in (\sqrt{N},N]}\) の部分は，同類項でまとめると \(\sqrt{N}\)個． なぜなら， \(i > \sqrt{N}\) のとき， \(0 < \lfloor \frac{N}{i} \rfloor \leq \frac{N}{i} < \sqrt{N}\) であるから．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n ;
cin >> n;
ll ans = 0;
for(ll i = 1; i <= n; ){
ll x = n/i;
ll ni = n/x+1;
ans += (ni-i)*x;
i = ni;
}
cout << ans << endl;
return 0;
}
