Сумма наибольших нечетных делителей первых 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

Я считаю, что они пытаются использовать следующие факты:

• е (2k + 1) = 2k + 1, то есть самый большой нечетный делитель из нечетного числа есть число сам.
• f (2k) = f (k). т. е. наибольший нечетный делитель четного числа 2т совпадает с наибольшим нечетным делителем числа т.
• Сумма первых k нечетных чисел равна k^2.

Теперь раскол {1,2, ..., 2m + 1} как {1,3,5,7, ...} и {2,4,6, ..., 2m} и попробуйте применить приведенные выше факты.

Answer 2

Я не вижу, как этот алгоритм может работать для описанной вами проблемы. (Я собираюсь предположить, что «N» и «n» относятся к одной и той же переменной).

Учитывая, п = 12.

Самый большой нечетный делитель равен 3 (остальные равны 1, 2, 4, 6 & 12)

F (12) является для них F (1) + F (2) + F (3) или 1 + 1 + 3 или 5.

Используя этот алгоритм:

к = (12 + 1)/2 или 6

и возвращаемся 6 * 6 + f (6), или 36 + некоторое число, которое не является goin г отрицательного 31.

Answer 3

если это 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 4

если и ищем сумму всех нечетных делителей до сих п ..

сумма всех нечетных делителей первых п чисел

...

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

для суммы всех делителей в диапазоне от 1 до 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 5

Вы можете использовать динамический подход также с использованием вспомогательных пространств

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 else, если число равно, кроме степени 2, разделите его на 2, пока вы не получите нечетное значение, и добавьте, что нечетные суммы.