[CSA] Round #4 Odd Divisors

Odd Divisors

整数の問題です。ある区間に入る数字を割り切ることできる奇数の最大値を求める問題です。当然、奇数ならばその値が最大値です。

考え方

最初の方針

区間の奇数はそのまま足すだけなので、

\[ 1 + 3 + 5 + \cdots + 2n – 1 = n^2 \]

を利用することで奇数の和はすぐに計算できます。偶数が問題なんですが、\( 1000000000 \) までの偶数に対してあらかじめ求め、累積和を使おうと思ったんですが、メモリ不足でダメでした。

公式の解説

偶数の方は再帰関数を使って求めるみたいです。いまいち分かりませんでした。

偶数を \( 2 \) で割り続けると奇数になるので、それを利用していると思います。

\[2, 4, 6, 8, 10, 12, 14, 16, 18 \]

は、

\[1, 1, 3, 1, 5, 3, 7, 1, 9\]

となるので、

\[1 + 1 + 2^2 + 5^2\]

のように計算しているんでしょうか。

ソースコード

シェアする

  • このエントリーをはてなブックマークに追加

フォローする