Editorial for Disjoint Set of Common Divisors


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

x, y son coprimos si y solo si gcd(x, y) = 1. Además se cumple gcd (a, x) \le gcd (a \cdot b, x). Por lo tanto, en lugar de elegir un número entero a \cdot b (a, b> 1), es mejor elegir a (Nota: si a \cdot b es un divisor común, entonces a también es un divisor común). Ese es, dada una solución óptima P, si un número entero a \cdot b (a, b> 1) estuviera contenido en los divisores comunes seleccionado en P, entonces puede elegir a en su lugar. Por lo tanto, existe una solución óptima que solo consta de 1 y primos. Además, tú puede elegir todos los divisores comunes que sea 1 o un primo, por lo que es óptimo elegir todos ellos. Entonces, ¿cómo podemos encontrar tales divisores comunes? Una forma en que la consideración y la implementación son ambos fáciles es factorizar A, B en factores primos (tomará un total de O (\max({\sqrt{A}, \sqrt{B}})) tiempo cada uno) y encuentre los factores primos comunes. El número de factores primos es O (log A), O (log B) cada uno, para que pueda encontrar los factores primos comunes ingenuamente a tiempo. Es óptimo elegir 1 y factores primos comunes, por lo que la respuesta será el número de factores primos comunes sumados por 1.

Con un poco más de consideración, parece que x es un divisor común de A y B si y solo si x es un divisor de gcd (A, B), entonces puedes factorizar gcd (A, B) en factores primos y contar los número de factores primos. Esto deja un tiempo de O (\min({\sqrt{A}, \sqrt{B}}))


Comments

There are no comments at the moment.