# Maybe you already know this problem (divisors) 75/100

**URL:** <https://forum.olinfo.it/t/maybe-you-already-know-this-problem-divisors-75-100/8567>\
**Category:** Aiuto\
**Created:** [29 Ottobre 2023, 2:12pm UTC](https://forum.olinfo.it/t/maybe-you-already-know-this-problem-divisors-75-100/8567 "2023-10-29T14:12:46Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Drayax](https://forum.olinfo.it/user_avatar/forum.olinfo.it/drayax/32/1452_2.png) [@Drayax](https://forum.olinfo.it/u/Drayax)\
**Post date:** [29 Ottobre 2023, 2:12pm UTC](https://forum.olinfo.it/t/maybe-you-already-know-this-problem-divisors-75-100/8567/1 "2023-10-29T14:12:46Z")

</div>

ho fatto tutto il possibile per le mie competenze, fare 100/100 va al di fuori. ho scritto il seguente codice:

 ![code](https://forum.olinfo.it/uploads/default/original/2X/c/c76ed298f474044673798475cdf5ac41c3b9c57c.png)

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ò:

 ![immagine_2023-10-29_145751972](https://forum.olinfo.it/uploads/default/original/2X/d/d6a8ef202ad31681b9577fa0c896779e00df860d.png)  
tutto il subtask 5 va in TLE, quindi probabilmente c’è una formula generale che ti fa risparmiare molti passi arrivando a O(log(n)) mi aiutate a trovarla?

---

<div class="post-metadata">

**Author:** ![fve5](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fve5/32/3229_2.png) [@fve5](https://forum.olinfo.it/u/fve5)\
**Post date:** [29 Ottobre 2023, 6:28pm UTC](https://forum.olinfo.it/t/maybe-you-already-know-this-problem-divisors-75-100/8567/2 "2023-10-29T18:28:35Z")

</div>

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\}.

---

<div class="post-metadata">

**Author:** ![Drayax](https://forum.olinfo.it/user_avatar/forum.olinfo.it/drayax/32/1452_2.png) [@Drayax](https://forum.olinfo.it/u/Drayax)\
**Post date:** [30 Ottobre 2023, 6:27am UTC](https://forum.olinfo.it/t/maybe-you-already-know-this-problem-divisors-75-100/8567/3 "2023-10-30T06:27:28Z")

</div>

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}]\}.

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [31 Ottobre 2023, 7:38pm UTC](https://forum.olinfo.it/t/maybe-you-already-know-this-problem-divisors-75-100/8567/4 "2023-10-31T19:38:29Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Drayax](https://forum.olinfo.it/user_avatar/forum.olinfo.it/drayax/32/1452_2.png) [@Drayax](https://forum.olinfo.it/u/Drayax)\
**Post date:** [18 Febbraio 2024, 11:41pm UTC](https://forum.olinfo.it/t/maybe-you-already-know-this-problem-divisors-75-100/8567/5 "2024-02-18T23:41:46Z")

</div>

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:

```auto
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 😄