Editorial for El cumpleaños de Ponyo

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: dcordb

El problema pide hallar para cada número $x$ ~x~ de la entrada cuantos números $y$ ~y~ hay tal que $y$ ~y~ divide a $x$ ~x~. Para esto podemos hallar la frecuencia de cada número en el arreglo y hacer algo parecido a una Criba de Eratóstenes:

for(int i = 1; i < MAX; i++)
    for(int j = i; j < MAX; j += i)
        sol[j] += freq[i]; //freq[i] es la frecuencia del número i

Lo que quedaría sería imprimir $sol[a[i]] - 1$ ~sol[a[i]] - 1~ para cada $i \; (1 \leq i \leq n)$ ~i \; (1 \leq i \leq n)~.

Complejidad: $O(MAX \log MAX)$ ~O(MAX \log MAX)~. Esto es porque se puede demostrar que para un natural $n$ ~n~ se cumple que $n + n / 2 + n / 3 + \ldots + 1 = O(n \log n)$ .

Comments

There are no comments at the moment.