前n个数的最大奇数除数之和

Question

我最近一直在使用topcoder,我偶然发现了一个我无法理解的问题.问题是找到给定"n"的F(n)= f(1)+ f(2)+ .... + f(n),使得f(n)是n的最大奇数除数.答案有很多简单的解决方案; 但是,我发现这个解决方案非常有趣.

int compute(n) {
if(n==0) return 0;
long k = (n+1)/2;
return k*k + compute(n/2);
}

但是,我不太明白如何从诸如此类的问题语句中获取递归关系.有人可以帮忙吗？

Answer 1

我相信他们正试图使用​​以下事实:

• f(2k + 1)= 2k + 1,即奇数的最大奇数除数是数字本身.
• f(2k)= f(k).即,偶数2m的最大奇数除数与数m的最大奇数除数相同.
• 第一个k个奇数的和等于k ^ 2.

现在将{1,2,...,2m + 1}拆分为{1,3,5,7,...}和{2,4,6,...,2m}并尝试应用上述事实.