AtCoderBeginnerContest230 E問題500点 「Fraction Floor Sum」
https://gyazo.com/83df7a2ec990e4b4f64f261c77fc730d
問題概要
制約
$ N \leq 10^{12}
解法・お気持ち
数学的な解放は公式の解説を参照してください。
ここから以下では、ganyariya のように数学が苦手な人間がコンテスト中になんとかする方法を書きます。
問題文は以下の値を求めろというものです。
$ \sum_{i=1}^N \lfloor \frac{N}{i} \rfloor
上記の形状は「よく見る形だなぁ」というものです。
こんなシンプルな計算式が絶対にはじめてなわけがない! という強い気持ちになります。
ここから3つパターンがあります。
1. 自分でがんばって立式する
2. インターネットで Keyword 検索する (sum 1 to N N / i)
3. OEIS をみる
OEIS は 整数列を与えると、有名な公式や性質を検索してくれる整数大辞典です。
OEIS で 1~10 までの問題文の値を調べると以下のページが検索できます。
code: go
for i := 1; i <= 10; i++ {
s := 0
for j := 1; j <= i; j++ {
s += i / j
}
fmt.Printf("%d,", s)
}
f(x) を計算する計算式が乗っています。
よって、これを解読して実装すればいいです。($ \LaTeX でないので読みづらいですね...)
計算量
$ O(1)
新たな学び
反省点
コード
code: go
func main() {
io := NewIo()
defer io.Flush()
// ------------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------
N := int64(io.NextInt())
sq := int64(math.Sqrt(float64(N)))
ans := int64(0)
for i := int64(1); i <= sq; i++ {
ans += 2 * (N / i)
}
ans -= sq * sq
fmt.Println(ans)
}