algorithm - 前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} 并尝试应用以上事实。