ABC172D - Sum of Divisors

【関連】

• ABC230E - Fraction Floor Sum - 競プロはじめました

方法1：エラトステネスの篩（ふるい）

考え方

約数を考える問題では，逆に「$i$の倍数で条件を満たすもの」に着目するのが典型的な解き方．例えば，

• エラトステネスの篩（ふるい）

そこで，次に気づくと解ける．

• エラトステネスの篩（ふるい）形のループは，$O(N \log N)$で実行できる．
• 求める和は，$1 \leq i \leq N$の倍数$j$で$1 \leq j \leq N$の範囲にあるものを，順に足し上げたものになっている．

回答例

N = int(input())

ans = 0
for i in range(1, N + 1):
  for j in range(i, N + 1, i):
    ans += j
print(ans)    

方法2：等差数列の和

考え方

上で，2コ目のループは「等差数列の和」を計算していることになる．したがって，これを直接

\begin{aligned}
& i \times \frac{a(a + 1)}{2} \\
& (a = \lfloor N / i \rfloor )
\end{aligned}

で計算すれば$O(1)$で済み，全体としては$O(N)$で解ける．

つまり，$i$の倍数で$[1,N]$の範囲にある個数を$g(i)$とするとき

\begin{aligned}
&\sum_{i=1}^{N} i \times g(i) \\
& g(i) = \frac{\lfloor N / i \rfloor (\lfloor N / i \rfloor + 1)}{2}
\end{aligned}

を計算する問題になった．

回答例

N = int(input())

ans = 0
for i in range(1, N + 1):
  a = N // i
  ans += i * a * (a + 1) // 2
print(ans)    

方法3：和を√Nで分割

考え方

ABC230E (ABC230E - Fraction Floor Sum - 競プロはじめました) の考え方を使えば，$O(\sqrt{N})$で解ける．

つまり，$h(a) = a(a+1) / 2$，$\mathrm{cnt\,}(a)= $「$\lfloor N / i \rfloor = a$を満たす$i$の個数」，$\mathrm{sum_{i}\,}(a)=$「$\lfloor N / i \rfloor = a$を満たす$i$の和」とすると，$\sum_{i} i\cdot g(i) = \sum_{a} \mathrm{sum_{i}\,}(a) \cdot h(a)$であり，

• $i \leq \sqrt{N}$では$\sum_{i} i\cdot g(i)$を$O(\sqrt{N})$で計算し
• $i >\sqrt{N}$では$\sum_{a} \mathrm{sum_{i}\,}(a) \cdot h(a)$を$O(\sqrt{N})$で計算する

と全体で$O(\sqrt{N})$で解ける．

回答例

N = int(input())

ans = 0
i = 1
while i ** 2 <= N:
  a = N // i
  ans += i * a * (a + 1) // 2
  i += 1

a -= 1
while a >= 1:
  cnt = (N // a) - (N // (a + 1))
  i_max = i + cnt - 1
  sum_i = ((i_max * (i_max + 1)) - (i - 1) * i) // 2
  ans += sum_i * a * (a + 1) // 2
  i += cnt
  a -= 1
 
print(ans)