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 de la entrada cuantos números y hay tal que y divide a 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 para cada i \; (1 \leq i \leq n).

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


Comments

There are no comments at the moment.