plus grand diviseur commun dans un intervalle

Soit x et y deux nombres. Dans ce cas, x est dit diviseur de y si y renvoie un reste nul lorsqu’il est divisé par x. Le plus grand diviseur présent dans un intervalle est le diviseur du plus grand nombre d’éléments de l’intervalle.

Énoncé du problème

Étant donné un intervalle [a, b]. Recherchez le plus grand diviseur qui apparaît dans la plage contenant a et b (autre que « 1 »). Renvoie 1 si tous les diviseurs apparaissent le même nombre de fois.

Exemple 1

Input [2, 5]

Output 2

Explication - Diviseurs de 2 = {1, 2}, diviseurs de 3 = {1, 3}, diviseurs de 4 = {1, 2, 4}, diviseurs de 5 = {1, 5} . 2 est le diviseur le plus fréquent.

Exemple 2

Input [2, 5]

Output 2

Explication - Diviseurs de 2 = {1, 2}, diviseurs de 3 = {1, 3}, diviseurs de 4 = {1, 2, 4}, diviseurs de 5 = {1, 5} . 2 est le diviseur le plus fréquent.

Méthode 1 : Fissuration par force brute

Un moyen brutal de résoudre ce problème consiste à trouver tous les diviseurs de tous les nombres dans l'intervalle et à les stocker sur une carte avec le nombre d'occurrences.

Algorithme

Diviseur de processus (num)

• Pour i = 1 à n1/2+1

• Si num%i == 0

• Si num/i == i

• Si je ne suis pas sur la carte, insérez (i, 1)

• Sinon map[i]++

• Autres

• Si je ne suis pas sur la carte, insérez (i, 1)

• Sinon map[i]++

• Si num/i n'est pas dans la carte, insérez (num/i, 1)

• Autres cartes[num/i]++

Traitement maxDivisors (a, b)

• pour n = a à b

• Diviseur (n)

• map.erase(1)

• diviseur = 1, nombre = int_min

• Pour chaque élément de la carte

• if it.value > count

• count = it.value

• Diviseur = it.key

Exemple : implémentation C++

Dans le programme ci-dessous, nous trouvons le diviseur de chaque nombre dans la fonction divisors() et trouvons le plus grand diviseur existant dans la fonction maxdivisor().

#include <bits/stdc++.h>
using namespace std;

// map storing occurrence of each divisor
unordered_map<int, int> occ;

// function to find all the divisors of a number and store it in map
void divisors(int num){
   for (int i = 1; i <= (sqrt(num) + 1); i++)    {
   
      // checking if i is divisor of num
      if (num % i == 0)        {
      
         // checking if num has identical divisors i.e. if i*i == num
         // if identical divisors then save only one
         if (num / i == i) {
            if (occ.find(i) == occ.end()) {
               occ.insert(make_pair(i, 1));
            }
            else{
               occ[i]++;
            }
         }
         else{
         
            // saving divisor i
            if (occ.find(i) == occ.end()) {
               occ.insert(make_pair(i, 1));
            }
            else{
               occ[i]++;
            }
            
            // saving the divisor of num corresponding to i
            if (occ.find(num / i) == occ.end()) {
               occ.insert(make_pair(num / i, 1));
            }
            else{
               occ[num / i]++;
            }
         }
      }
   }
}

// function to find maximum occurring divisor in an interval
int maxDivisor(int a, int b){
   for (int n = a; n <= b; n++){
      divisors(n);
   }
   
   // deleting all occurrences of 1 as 1 is not to be returned until the interval is [1,1]
   occ.erase(1);
   
   // divisor set as 1 for edge case scenario when interval is [1,1]
   int div = 1, cnt = INT_MIN;
   for (auto it = occ.begin(); it != occ.end(); it++) {
      if (it->second > cnt) {
         cnt = it->second;
         div = it->first;
      }
   }
   return div;
}
int main(){
   int a = 4, b = 7;
   cout << "For the interval [" << a << ", " << b << "] maximum occurring divisor = ";
   cout << maxDivisor(a, b);
   return 0;
}

Sortie

For the interval [4, 7] maximum occurring divisor = 2

Complexité temporelle - O(n3/2), car pour chaque nombre de l'intervalle, pour trouver le diviseur, une boucle de complexité O(n1/2) est effectuée.

Complexité spatiale - O(n), espace cartographique.

Méthode 2

La méthode ci-dessus peut être encore optimisée en réduisant le temps nécessaire pour remplir la carte à chaque occurrence du diviseur. Au lieu de trouver le diviseur de chaque nombre, vous pouvez connaître l’occurrence de chaque diviseur dans l’intervalle en calculant les limites inférieure et supérieure de l’intervalle.

Prenons l'intervalle [2, 5] comme exemple.

L'ensemble des diviseurs possibles est de 1 à 5. Par conséquent, 1 = 5/1 - 2/1 +1 = 4 se produit. Il semble que 2 = 5/2 - 2/2 + 1 = 2. Il semble que 3 = 5/3 - 2/3 = 1. Il semble que 4 = 5/4 - 2/4 = 1. Il semble que 5 = 5/5 - 2/5 = 1.

Ce qui précède peut être formalisé comme suit :

Si limite inférieure% diviseur == 0 alors occ = limite supérieure/diviseur - limite inférieure/diviseur + 1

Autre occ = limite supérieure/diviseur - limite inférieure/diviseur

Algorithme

Traitement maxDivisor (a, b)

• pour i = 2 à b

• Si a%i == 0

• Nombre de fois = b/i - a/i +1

• Autres

• Nombre de fois = b/i - a/i

• map.insert(i, fois)

• diviseur = 1, nombre = int_min

• Pour chaque élément de la carte

• if it.value > count

• count = it.value

• Diviseur = it.key

Exemple : implémentation C++

Dans le programme ci-dessous, au lieu de trouver les diviseurs d'un nombre dans l'ordre inverse, on trouve pour chaque diviseur combien de multiples il a dans l'intervalle.

#include <bits/stdc++.h>
using namespace std;

// function to find maximum occurring divisor in an interval
int maxDivisor(int a, int b){

   // map used to store occurrences of divisors
   unordered_map<int, int> occ;
   for (int i = 2; i <= b; i++){
      int times;
      if (a % i == 0){
         times = (b / i) - (a / i) + 1;
      }
      else{
         times = (b / i) - (a / i);
      }
      occ.insert(make_pair(i, times));
   }

   // divisor set as 1 for edge case scenario when interval is [1,1]
   int div = 1, cnt = INT_MIN;
   for (auto it = occ.begin(); it != occ.end(); it++){
      if (it->second > cnt){
         cnt = it->second;
         div = it->first;
      }
   }
   return div;
}
int main(){
   int a = 1, b = 10;
   cout << "For the interval [" << a << ", " << b << "] maximum occurring divisor = ";
   cout << maxDivisor(a, b);
   return 0;
}

Sortie

For the interval [1, 10] maximum occurring divisor = 2

Méthode 3

Une solution très simple à ce problème est présentée ci-dessous,

Dans tout intervalle de taille > 1, la moitié des nombres (chaque nombre pair) aura 2 comme diviseur.

Il peut donc être utilisé comme suit.

Algorithme

Traitement maxDivisors (a, b)

• si a == b

• ans = a

• Autres

• ans = 2

Exemple : implémentation C++

Dans le programme ci-dessous, nous implémentons l'observation selon laquelle tout nombre pair a 2 comme diviseur.

#include <bits/stdc++.h>
using namespace std;

// function to find the maximum occurring divisor in an interval
int maxDivisor(int a, int b){
   if (a == b){
      return a;
   } else {
      return 2;
   }
}
int main(){
   int a = 1, b = 10;
   cout << "For the interval [" << a << ", " << b << "] maximum occurring divisor = ";
   cout << maxDivisor(a, b);
   return 0;
}

Sortie

For the interval [1, 10] maximum occurring divisor = 2

Conclusion

En bref, afin de trouver le plus grand diviseur présent dans un intervalle, nous pouvons utiliser la méthode ci-dessus, la plage temporelle va de O(n3/2) à O(1) et la plage spatiale va de O(n) à O (1).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!