ho fatto tutto il possibile per le mie competenze, fare 100/100 va al di fuori. ho scritto il seguente codice:
semplicemente ho usato la formula (n/1 + n/2 + ... + n/n) e ho anche ottimizzato mettendo un if che controlla quando la divisione riporta 1, essendo che in quel caso da li fino a n/n il risultato sarà sempre 1. Però:
La soluzione ottima non è O(\log N). Un buon punto di partenza per trovarla è considerare che 1 non è l’unico risultato che appare molte volte in \{\lfloor\frac{n}{1}\rfloor,\lfloor\frac{n}{2}\rfloor,\ldots \lfloor\frac{n}{n}\rfloor\}.
eh si ci avevo pensato, ma come faccio a capire un numero quante volte restituisce 2 o 3 in tutte le divisioni \{[\frac{n}{1}], [\frac{n}{2}], ...[\frac{n}{n}]\}.
Puoi pensarla così, supponi che stai cercando quanti x esistono tali che \lfloor \frac{n}{x} \rfloor = k, e quindi formi l’insieme D_k = \{x | \lfloor \frac{n}{x} \rfloor = k\}, quello che puoi “sfruttare” a tuo vantaggio è che tale insieme corrisponde all’insieme \{min(D_k), min(D_k) + 1, \dots, max(D_k) - 1, max(D_k)\}, ciò significa che, per ogni k, se tu fossi in grando di stabilire il minimo e il massimo valore di x per il quale vale \lfloor \frac{n}{x} \rfloor = k allora puoi ottenere D_k (o meglio ancora |D_k|). Per rendere l’idea se n = 100.000 e sono interessato a k = 2, se scopro che min(D_k) = 33.334, max(D_k) = 50.000 allora posso anche sapere che |D_k| = 50.000 - 33.334 + 1
dopo molto tempo ho risolto questo problema, do come soluzione fve perchè da quel messaggio mi è venuta l’illuminazione, comunque ho usato la ricerca binaria per trovare quanti numeri hanno come risultato n/i, quindi molto semplicemente ogni passo aumentavo sum di n/i * numero di numeri che hanno quel numero di divisori. questo è il codice:
ll sum = 0;
ll last_true(ll lo, ll hi, ll r, ll n) {
lo--;
while (lo < hi) {
ll mid = lo + (hi - lo + 1) / 2;
if (n/mid == r) {
lo = mid;
} else {
hi = mid - 1;
}
}
return lo;
}
ll compute(ll n){
ll i = 1;
while(i <= n){
ll last = last_true(i, n, n/i, n);
sum += (n/i) * (last - i + 1);
i = last + 1;
}
return sum;
}
ringrazio comunque tutti per l’aiuto 