前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);
}

然而，我不太明白如何从这样的问题陈述中获得递归关系。有人可以帮忙吗？

- user277465

---

这里的 f 和 compute 是同一件事吗？ - AakashM

@Aakash：不，它们不是（如果要正确的话），我已经编辑了问题。 - Aryabhatta

你打错了：你使用了 "N" 和 "n"，请修正。 - Jason S

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}，并尝试应用上述事实。

- Aryabhatta

Answer 2

你可以使用辅助空间来实现动态方法。

int sum=0;
int a[n+1];
for(int i=1;i<=n;i++){
  if(i%2!=0)
  a[i] = i;
  else
  a[i] = a[i/2];
}
for(int i=1;i<=n;i++){
  sum+=a[i];
}
cout<<sum;

当数字为奇数时，该数字本身将是最大的奇数因子，a[i]将存储它的值；当数字为偶数时，a[number/2]将被存储在a[i]中，因为对于偶数，number/2的最大奇数因子将是该数字的最大奇数因子。

也可以使用三种情况来解决：当数字为奇数时，加上该数字本身；如果数字是2的幂，则加上1；如果数字是偶数但不是2的幂，则除以2直到得到奇数，然后将该奇数加到总和中。

- Chetan Kumar

Answer 3

如果您正在寻找所有奇数因子的总和，直到n...

前n个数字的所有奇数因子的总和

...

for(long long int i=1;i<=r;i=i+2)
{
    sum1=sum1+i*(r/i);   
}

计算范围从l到r的所有因子之和

for(long long int i=1;i<=r;i=i+2)
{
    sum1=sum1+i*(r/i); 
}

for(long long int i=1;i<l;i=i+2)
{
    sum2=sum2+i*((l-1)/i); 
}

ans=sum1-sum2;;;

谢谢！

- Sumit Singh

Answer 4

如果这是Java，我会说：

 import java.util.*;
 int sum_largest_odd_factors (int n){
      ArrayList<Integer> array = new ArrayList();//poorly named, I know
      array.add(1);
      for(int j = 2; j <= n; j++){
           array.add(greatestOddFactor(j));
      }
      int sum = 0;
      for(int i = 0; i < array.size(); i++){
           sum += array.get(i); 
      }
      return sum;
 }
 int greatestOddFactor(int n){
      int greatestOdd = 1;
      for(int i = n-((n%2)+1); i >= 1; i-=2){
          //i: starts at n if odd or n-1 if even 
          if(n%i == 0){
               greatestOdd = i;
               break;
               //stop when reach first odd factor b/c it's the largest
          }
      }
      return greatestOdd;
 }

这无疑是一项单调乏味的工作，可能是O(n^2)的操作，但每次都能正常工作。我将把它留给您将其转换为C++，因为Java和J是我唯一能够使用的语言（即使在低级别上也是如此）。我很好奇其他人能想出什么巧妙的算法来加快这个过程。

- S_Lang

Answer 5

我看不出那个算法如何适用于你描述的问题。（我会假设“N”和“n”指的是同一个变量。）

给定 n = 12。

最大奇因子是 3（其他因子为 1、2、4、6 和 12）

F(12) 因此为 f(1) + f(2) + f(3) 或 1 + 1 + 3 或 5。

使用该算法：

k = (12+1)/2，即 6

我们返回 6 * 6 + f(6)，即 36 + 某个不会为负数的数字 31。

- James Curran

---

问题中的代码是错误的，我已经编辑了代码使其正确（请参阅我的答案以了解原因）。 - Aryabhatta