SPOJ 24032 - The art of tree numbers [TREENUM2]

Source

SPOJ 24032 [TREENUM2]

問題概要

異なる $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)$ ぐらい.

C言語によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります.


Current time: 2017年11月18日04時25分13秒
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)

ログイン: