差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2020:0627_abc172 [2020/06/27] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2020:0627_abc172 [2020/06/28] (現在) – [$O(\sqrt{N})$ 解法] ikatakos | ||
|---|---|---|---|
| 行 52: | 行 52: | ||
| n = int(input()) | n = int(input()) | ||
| ans = solve(n) | ans = solve(n) | ||
| + | print(ans) | ||
| + | </ | ||
| + | |||
| + | ==== $O(\sqrt{N})$ 解法 ==== | ||
| + | |||
| + | 上記のように「$N$ までに $a$ の倍数は $b$ 個ある」は $b = \dfrac{N}{a}$ で求められる。 | ||
| + | |||
| + | しかし、$b$ が小さい場合（1個や2個など）、$b$ が同じになる $a$ は数多く存在する。$b$ が小さい範囲については、それらをまとめて計算してやりたい。 | ||
| + | |||
| + | a \ x | ||
| + | 1 | ||
| + | 2 | ||
| + | 3 | ||
| + | 4 | ||
| + | 5 | ||
| + | 6 | ||
| + | 7 | ||
| + | 8 | ||
| + | ... | ||
| + | |||
| + | 「$N$ までに倍数が $b$ 個ある最大の $a$」は、$a = \dfrac{N}{b}$ で求められる。 | ||
| + | |||
| + | 要は $a \times b \le N$ なので、$\sqrt{N}$ 付近で $a,b$ の大小が切り替わる。 | ||
| + | |||
| + | $a \lt b$ の範囲は $a$ を中心に計算し、$a \gt b$ の範囲は $b$ を中心に計算すると、探索範囲の上限は $\sqrt{N}$ となる。 | ||
| + | |||
| + | 注意すべきは $a=b$ となるような場合で、重複して数えないようにする。 | ||
| + | |||
| + | $N$ までに倍数が $b$ 個ある最大の数を $q = \dfrac{N}{b}$、$b+1$ 個（以上）ある最大の数を $p=\dfrac{N}{b+1}$ とすると、 | ||
| + | $a=p+1, | ||
| + | |||
| + | これは、2つの等差数列の和のかけ算で、$\dfrac{(p+1+q)(q-p)}{2} \dfrac{b(b+1)}{2}$ で求められる。 | ||
| + | |||
| + | <sxh python> | ||
| + | n = int(input()) | ||
| + | ans = 0 | ||
| + | for i in range(1, int(n ** 0.5) + 1): | ||
| + | k = n // i | ||
| + | ans += i * k * (k + 1) // 2 | ||
| + | if i != k: | ||
| + | l = n // (i + 1) | ||
| + | ans += i * (i + 1) * (k + l + 1) * (k - l) // 4 | ||
| print(ans) | print(ans) | ||
| </ | </ | ||
