[CSA] Round #4 Odd Divisors
問題
https://csacademy.com/contest/beta-round-4/task/odd_divisors...ある区間における数字を割り切ることできる奇数の最大値の和を求める問題です。当然、奇数ならばその値が最大値です。
方針
区間の分割
区間 \( [A, B]\) における数字を割り切る奇数の最大値の和を \( f(A, B) \) とすると、
\[f(A, B) = f(B, 1) – f(A – 1, 1) \]
と表すことができます。ただし、\( A = 1 \) のときは、\( f(0, 1) = 0 \) とします。
和を求める
区間の奇数はそのまま足すだけなので、
\[ 1 + 3 + 5 + \cdots + 2n – 1 = n^2 \]
を利用することで奇数の和はすぐに計算できます。
\( f(1, n) \) の値を求めれば良いので、区間 \( [1, n]\) について考えます。\( [1, n] \) における奇数の個数 \( t \) は、\( \lfloor \dfrac{n + 1}{2} \rfloor \) となります。また、偶数の個数は \( n – t \) となります。
ここで、\( n = 10 \) の時を考えると、偶数は、\( 2, 4, 6, 8, 10 \) となり、\( 2 \) で割ると、\( 1, 2, 3, 4, 5 \) となるので、\( f(1, 10) = t * t + f(1, n – t) \) となります。よって、このように再帰関数を定義することで和を求めることができます。
コード
提出したコード
https://csacademy.com/submission/2211315/再帰関数
ll count(ll n) {
if (n == 0) return 0;
ll t = (n + 1) / 2;
return t * t + count(n - t);
}