Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-24

OddDivisors

| 21:02

問題文, SRM 449

f(x)をxの最大の奇除数とする。正の整数Nが与えられたとき、f(1)+f(2)+f(3)+...+f(N)を求めよ。

独力で解けなかったので、Panteraさんの解答を参考にしました。f(x)の1からf(N)までの和をS(N)とすると、その漸化式は次の通りです:

 S(N) = \{\array{ll$0\quad & \mbox{if}\quad{} N \quad{} \mbox{is}\quad 0,\\N+S(N-1)\quad & \mbox{if}\quad{}  N \quad \mbox{is} \quad \mbox{odd},\\(N/2)^2+S(N/2)\quad & \mbox{if}\quad{} N \quad \mbox{is}\quad \mbox{even}.\.

偶数の場合がこのような式になるのは、(N/2)+1からNのf(x)の値として、1から2(N/2)-1(=N-1)の全ての奇数が現れるためだと思います。

class OddDivisors {
public:
    long long findSum(int N) {
        if (N == 0) return 0;
        if (N%2 == 1) return N + findSum(N-1);
        long long h = N / 2;
        return h*h + findSum(h);
    }
};

CoralynCoralyn2011/07/11 02:35Heck yeah this is exactly what I neeedd.

gnblerevzcgnblerevzc2011/07/11 17:56uYLsg6 <a href="http://xastizaaaprn.com/">xastizaaaprn</a>

caszabcaszab2011/07/11 21:55uZUOLK , [url=http://bkzlqlrxqsvd.com/]bkzlqlrxqsvd[/url], [link=http://xoibmkylinnn.com/]xoibmkylinnn[/link], http://yipaejjalqbl.com/

dipyiedipyie2011/07/13 18:34IdrEYp <a href="http://ofalwtjxbsqh.com/">ofalwtjxbsqh</a>

kaedxpshifkaedxpshif2011/07/13 23:313Uxab3 , [url=http://wtysquibqpuq.com/]wtysquibqpuq[/url], [link=http://qbzcfinwlbfk.com/]qbzcfinwlbfk[/link], http://tykaxlxiebyk.com/