Сумма наибольших нечетных делителей первых n чисел

Question

Я недавно работал над topcoder и наткнулся на этот вопрос, который я не совсем понимаю.Вопрос состоит в том, чтобы найти F (n) = f (1) + f (2) + .... + f (n) для данного "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} и попробуйте применить приведенные выше факты.

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;

Так как, когда число нечетное, само число будет наибольшим нечетным делителем, а [i] будет хранить его значение, а когда число четное.тогда a [число / 2] будет сохранено в [i], потому что для четного числа наибольший нечетный делитель числа / 2 будет наибольшим нечетным делителем числа.

Это также можно решить с помощьюв трех случаях, когда число нечетное, добавьте еще одно число, если число является степенью 2, затем добавьте еще 1, если число четное, за исключением степени 2, разделите его на 2, пока не получите нечетное число, и добавьте это нечетное к сумме.

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;;;

СПАСИБО !!

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 - единственные языки, с которыми я могу работать (и даже на низком уровне). Мне интересно, какие гениальные алгоритмы могут придумать другие люди, чтобы сделать это намного быстрее.

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.