Somma dei maggiori divisori dispari dei primi n numeri

Question

Recentemente ho lavorato su topcoder e mi sono imbattuto in questa domanda che non riesco a capire. La domanda è di trovare F (n) = f (1) + f (2) + .... + f (n) per un dato "n" tale che f (n) è il più grande divisore dispari per n. Ci sono molte soluzioni banali per la risposta; tuttavia, ho trovato questa soluzione molto intrigante.

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

Tuttavia, non capisco come ottenere una relazione ricorsiva da un'affermazione del problema come questa. Qualcuno potrebbe dare una mano?

Answer 1

Credo che stanno cercando di utilizzare i seguenti fatti:

• f (2k + 1) = 2k + 1, ovvero il più grande divisore dispari di un numero dispari è il numero si.
• f (2k) = f (k). il più grande divisore dispari di un numero pari di 2m è uguale al più grande divisore dispari del numero m.
• La somma dei primi k numeri dispari è uguale a k^2.

Ora diviso {1,2, ..., 2m + 1} come {1,3,5,7, ...} e {2,4,6, ..., 2m} e prova ad applicare i fatti di cui sopra.

Answer 2

Non riesco a vedere come quell'algoritmo potrebbe funzionare per il problema che hai descritto. (Assumerò che "N" e "n" si riferiscono alla stessa variabile).

Dato n = 12.

Il grande divisore dispari è 3 (le altre sono 1, 2, 4, 6 & 12)

F (12) è per esso f (1) + f (2) + f (3) o 1 + 1 + 3 o 5.

Utilizzando questo algoritmo:

k = (12 + 1)/2 o 6

e ci ritorno 6 * 6 + f (6), o 36 + un numero che non sta andando g sia negativo 31.

Answer 3

se questo fosse Java, direi:

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

Questo è certamente noioso e probabilmente un O (n^2) il funzionamento, ma funziona ogni volta. Lascio a te la traduzione in C++ come Java e J sono le uniche lingue con cui posso lavorare (e anche quelle a basso livello). Sono curioso di sapere quali algoritmi ingegnosi gli altri possano inventare per renderlo molto più veloce.

Answer 4

se u sono alla ricerca di somma di tutti i divisori dispari fino al n ..

somma dei tutti i divisori dispari dei primi n numeri

...

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

per sum di tutti i divisori in un intervallo da l a 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;;; 

GRAZIE !!

Answer 5

È possibile utilizzare approccio dinamico utilizzando anche spazi ausiliari

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; 

Come quando il numero è dispari, allora il numero stesso sarà la più grande divisore dispari e a [i] memorizzerà il suo valore e quando il numero è anche in questo caso il [numero/2] sarà memorizzato in un [i] perché per il numero pari il massimo divisore dispari di numero/2 sarà il massimo divisore dispari del numero.

Si può anche risolvere usando tre casi quando il numero è dispari quindi aggiungi il numero stesso se il numero è potere di 2 quindi aggiungi 1 altro se il numero è pari ad eccezione della potenza di 2 dividi per 2 fino a ottenere dispari e aggiungi quello da dispari a somma.