OMC057(C)

点数: 500

Writer: shakayami

　非負整数に対して定義される関数 $f$ は, $f(0)=0$ および正整数 $n$ に対して $$f(n)=\begin{cases} f(n/2) & (n\ \text{が偶数のとき}) \\ f((n-1)/2)+1 & (n\ \text{が奇数のとき}) \end{cases}$$ をみたします. このとき, $N=2^{20}-1(=1048575)$ に対し以下の総和 $$M=\sum_{n=0}^{2^N-1}nf(n)$$ が $2$ で割り切れる最大の回数を求めてください.