異なる $3$ のべき乗の正整数の和として得られる正整数をTREE NUMと呼ぶ．
TREE NUMのうちで，小さい方から $k$ 番目のものを $T_k$ と書く．
$\quad \displaystyle \sum_{k=L}^R T_k$
を ${\rm mod}\ 2^{32}$ で求める問題．
いつもどおり，
$\quad \displaystyle f(N) = \sum_{k=1}^N T_k$
として，$f(R)-f(L-1)$ を求めれば良い．
$T_k$ は $k$ を $2$ 進数表示して，それを $3$ 進数だと解釈した値となる．
よって，$1$ から $R$ までを $2$ 進数表記した時に，$2^i$ の桁に何個 $1$ があるかを求めて，その数と $3^i$ の積を足していけば良い．
$2^i$ の桁に何個 $1$ があるかは，$2^i$ の桁に関する周期性を用いれば計算できる．
時間計算量は $O(T \log R)$ ぐらい．
この部分を表示するには表示権限を持つユーザーでログインする必要があります．
Current time: 2024年04月25日08時05分50秒
Last modified: 2015年06月15日14時48分32秒 (by laycrs)
Tags: Competitive_Programming Sphere_Online_Judge SPOJ_Classical
トップページに戻る
Logged in as: unknown user (not login)