Editorial for Divisores.


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.

Authors: humbertoyusta

Primera subtarea:

Para esta subtarea podemos factorizar todos los números y calcular el número de divisores con la siguiente fórmula

\(CntD (x) = \sum_{p \in F}( 1 + p + ... + p^e )\)

Donde \(F\) es el conjunto de todos los factores primos de \(x\), y \(e\) es la mayor potencia de \(p\) que divide a \(x\).

Esta fórmula se puede simplificar a:

\(CntD (x) = \sum_{p \in F}\frac{p^{e+1}-1}{p-1}\)

Aplicando la fórmula de progresión aritmética. La cual dice que \(a^0 + a^1 + a^2 + ... + a^n = \frac{a^{n+1}-1}{a-1}\)

Segunda Subtarea:

Aquí no podemos factorizar, hay números que son el producto de dos primos, otros que son potencias de un primo, estos segundos son fáciles de tener en cuenta para la solución, con los primeros tenemos que tener mas cuidado, e intentar ver su \(gcd\) con otros números para factorizarlos bien, y los que sean coprimos con todos los demás y no sean potencia de primo, los valores de sus primos no son relevantes, ya que son dos y solo están presentes en él o en otros elementos iguales, solo importa la cantidad de veces que está el número. Con esto podemos construir la respuesta, para más detalle el siguiente link.

D-divisors


Comments


  • 1
    Sekai02  commented on April 6, 2021, 5:34 p.m. edited

    humbertoyusta en la parte que dices:

    "estos segundos son fáciles de tener en cuenta para la solución, para los segundos tenemos que tener mas cuidado" creo que te equivocaste al escribir o que lo podias haber redactado de una manera menos confusa. Revisa eso.


    • 2
      humbertoyusta  commented on April 6, 2021, 7:06 p.m.

      Arreglado, gracias