Plus grand GCD entre certains nombres
Nous avons des nombres positifs. Nous voulons trouver la paire avec un maximum de pgcd. en fait, ce maximum est plus important que la paire!
Par exemple, si nous avons:
2 4 5 15
pgcd(2,4)=2
pgcd(2,5)=1
pgcd(2,15)=1
pgcd(4,5)=1
pgcd(4,15)=1
pgcd(5,15)=5
La réponse est 5.
source d'informationauteur
Vous devez vous connecter pour publier un commentaire.
Il y a une solution qui permettrait de prendre en O(n):
Laisser nos numéros
a_i
. Tout d'abord, calculerm=a_0*a_1*a_2*...
. Pour chaque numéro, a_i, calculergcd(m/a_i, a_i)
. Le numéro que vous cherchez est le maximum de ces valeurs.Je n'ai pas prouvé que cela est toujours vrai, mais dans votre exemple, il travaille:
m=2*4*5*15=600,
max(gcd(m/2,2), gcd(m/4,4), gcd(m/5,5), gcd(m/15,15))=max(2, 2, 5, 5)=5
REMARQUE: Ce n'est pas correct. Si le nombre
a_i
a un facteurp_j
répété deux fois, et si les deux autres numéros contiennent également ce facteur,p_j
alors vous obtenez le résultat incorrectp_j^2
place dep_j
. Par exemple, pour la mise en3, 5, 15, 25
vous obtenez25
comme la réponse au lieu de5
.Cependant, vous pouvez toujours l'utiliser pour filtrer rapidement le nombre. Par exemple, dans le cas ci-dessus, une fois que vous déterminer les 25, vous pouvez d'abord faire la recherche exhaustive de
a_3=25
avecgcd(a_3, a_i)
à trouver le vrai maximum,5
puis filtrergcd(m/a_i, a_i), i!=3
qui sont inférieures ou égales à5
(dans l'exemple ci-dessus, ce filtre tous les autres).Ajouté pour plus de précision et de justification:
De voir pourquoi cela devrait fonctionner, notez que
gcd(a_i, a_j)
divisegcd(m/a_i, a_i)
pour tousj!=i
.Appelons
gcd(m/a_i, a_i)
commeg_i
etmax(gcd(a_i, a_j),j=1..n, j!=i)
commer_i
. Ce que je dis ci-dessus estg_i=x_i*r_i
etx_i
est un entier. Il est évident quer_i <= g_i
donc dansn
pgcd des opérations, on obtient une limite supérieure pour lesr_i
pour tousi
.Au-dessus de la réclamation n'est pas très évident. Nous allons examiner un peu plus en profondeur pour voir pourquoi c'est vrai: le pgcd de
a_i
eta_j
est le produit de tous les facteurs premiers qui apparaissent dans les deuxa_i
eta_j
(par définition). Maintenant, multiplieza_j
avec un autre numéro,b
. Le pgcd dea_i
etb*a_j
est égale àgcd(a_i, a_j)
ou est un multiple de celui-ci, parce queb*a_j
contient tous les facteurs premiers dea_j
et un peu plus de facteurs premiers contribué parb
qui peuvent également être inclus dans la factorisation dea_i
. En fait,gcd(a_i, b*a_j)=gcd(a_i/gcd(a_i, a_j), b)*gcd(a_i, a_j)
je pense. Mais je ne peux pas voir un moyen de rendre l'utilisation de ce. 🙂De toute façon, dans notre construction,
m/a_i
est simplement un raccourci pour calculer le produit de tousa_j
oùj=1..1, j!=i
. En conséquence,gcd(m/a_i, a_i)
contient tous lesgcd(a_i, a_j)
comme un facteur. Alors, évidemment, le maximum de ces pgcd résultats seront diviserg_i
.Maintenant, le plus grand
g_i
est d'un intérêt particulier pour nous: c'est soit le maximum pgcd lui-même (six_i
est de 1), ou un bon candidat pour être un. Pour ce faire, nous faisons un autren-1
pgcd des opérations, et de calculerr_i
explicitement. Puis, nous sortons tous lesg_j
inférieure ou égale àr_i
en tant que candidats. Si nous n'avons pas de n'importe quel autre candidat de gauche, nous sommes fait. Si non, nous reprenons la prochaine plus grandeg_k
et de calculerr_k
. Sir_k <= r_i
nous goutteg_k
et répétez avec l'autreg_k'
. Sir_k > r_i
on filtre lesg_j <= r_k
et répétez.Je pense qu'il est possible de construire un ensemble de nombres qui feront de cet algorithme s'exécuter en O(n^2) (si nous ne parvenons pas à filtrer quoi que ce soit), mais sur des ensembles de nombres aléatoires, je pense qu'il va vite se débarrasser de gros morceaux de candidats.
Vous pouvez utiliser l'Algorithme d'Euclide pour trouver le PGCD de deux nombres.
Si vous voulez une alternative à l'évidence de l'algorithme, et en supposant que vos numéros sont dans un délimitée de la plage, et vous avez beaucoup de mémoire, vous pouvez battre O(N^2), N étant le nombre de valeurs:
Qui vous indique le max gcd, mais ne vous dit pas quelle paire produite. Pour votre exemple de saisie, le calcul de la matrice de ressemble à ceci:
Je ne sais pas si c'est fait plus vite pour les entrées que vous avez à gérer. La constante de facteurs en jeu sont importantes: la limite de vos valeurs et le temps de factorise une valeur à l'intérieur de cette limite.
Vous n'avez pas à factorise chaque valeur que vous pourriez utiliser memoisation et/ou un préfabriqués liste des nombres premiers. Ce qui me donne l'idée que si vous êtes memoising la factorisation, vous n'avez pas besoin de la matrice:
Ajouter/recherche dans un ensemble pourrait être O(log N), bien que cela dépend de ce que la structure de données que vous utilisez. Chaque valeur est O(f(k)) des facteurs, où k est la valeur max et je ne me souviens pas ce que la fonction f est...
La raison que vous avez terminé avec une valeur dès que vous le rencontrez dans le jeu est que vous avez trouvé un nombre qui est un facteur commun des deux valeurs d'entrée. Si vous gardez factorising, vous ne trouverez plus petit de ces nombres, qui ne sont pas intéressantes.
Je ne suis pas sûr que le meilleur moyen est de répéter pour les plus grands facteurs. Je pense que, dans la pratique, vous pourriez avoir à trouver un équilibre: vous ne voulez pas faire tout à fait dans l'ordre décroissant, parce que c'est maladroit de générer commandé facteurs, mais vous ne voulez pas de trouver réellement de tous les facteurs.
Même dans les royaumes de O(N^2), vous pourriez être en mesure de battre l'utilisation de l'algorithme d'Euclide:
Entièrement factorise chaque numéro, le stockage comme une séquence d'exposants des nombres premiers (donc pour l'exemple 2, {1}, 4 est de {2}, 5 {0, 0, 1}, 15 est {0, 1, 1}). Ensuite, vous pouvez calculer pgcd(a,b) en prenant la valeur min à chaque indice et de les multiplier, de retour. Aucune idée si c'est plus rapide que d'Euclide sur la moyenne, mais il pourrait être. Évidemment, il utilise une charge de plus de mémoire.
Des optimisations, je pense,
1) commencer par les deux plus grands nombres, car ils sont susceptibles d'avoir la plupart des facteurs premiers, et donc les plus susceptibles d'avoir partagé facteurs premiers (et donc de la plus haute PGCD).
2) Lors du calcul de la GCDs d'autres paires que vous pouvez arrêter votre algorithme d'Euclide boucle si vous restez en dessous de votre plus grand PGCD.
Sur le dessus de ma tête, je ne peux pas penser à une façon que vous pouvez travailler sur la plus grande PGCD d'une paire sans même essayer de travailler sur chaque paire individuellement (et d'optimiser un peu comme ci-dessus).
Avertissement: je n'ai jamais regardé ce problème avant et le dessus est en haut de ma tête. Il peut y avoir de meilleures façons et j'ai peut-être tort. Je suis heureux de discuter de mes pensées en plus de la longueur si quelqu'un veut. 🙂
Il n'y a pas de
O(n log n)
solution à ce problème en général. En fait, dans le pire des casO(n^2)
dans le nombre d'éléments dans la liste. Considérer l'ensemble des nombres:Seulement le PGCD des deux derniers est supérieur à 1, mais la seule façon de savoir que de regarder la GCDs est d'essayer chaque paire et remarquez que l'un d'entre eux est plus grand que 1.
Donc, vous êtes coincé avec le ennuyeux force brute essayer à chaque paire d'approche, peut-être avec un couple de clever optimisations pour éviter de faire un travail inutile quand vous l'avez déjà trouvé un grand PGCD (en vous assurant que vous ne manquiez de rien).
Avec certaines contraintes, e.g les chiffres dans le tableau sont à l'intérieur d'une plage donnée, disons 1-1e7, c'est faisable en O(NlogN) /S(MAX) * logMAX), où MAX est la valeur maximale possible dans A.
Inspirés par le tamis de l'algorithme, et est venu à travers elle dans un Hackerrank Défi -- là, il est fait pour les deux tableaux. Vérifier leur rédaction.
créer un masque binaire, pour marquer les éléments apparaissent dans la plage donnée, pour O(1) recherche; O(N) pour construire; O(MAX_RANGE) de stockage.
pour aa = a; aa < max(A); aa += a:
Réponse précédente:
Toujours O(N^2) -- trier le tableau; devrait éliminer certains des comparaisons inutiles;
Cela devrait enregistrer certains de calculs inutiles.
pseudocode