größter gemeinsamer Teiler in einem Intervall

Seien x und y zwei Zahlen. In diesem Fall wird x als Teiler von y bezeichnet, wenn y bei der Division durch x einen Rest von Null zurückgibt. Der größte in einem Intervall vorkommende Teiler ist der Teiler der größten Anzahl von Elementen im Intervall.

Problemstellung

Gegebenes Intervall [a, b]. Finden Sie den größten Teiler, der in dem Bereich auftritt, der a und b enthält (außer „1“). Gibt 1 zurück, wenn alle Teiler gleich oft vorkommen.

Beispiel 1

Input [2, 5]

Output 2

Erklärung - Teiler von 2 = {1, 2}, Teiler von 3 = {1, 3}, Teiler von 4 = {1, 2, 4}, Teiler von 5 = {1, 5}. 2 ist der häufigste Teiler.

Beispiel 2

Input [2, 5]

Output 2

Erklärung - Teiler von 2 = {1, 2}, Teiler von 3 = {1, 3}, Teiler von 4 = {1, 2, 4}, Teiler von 5 = {1, 5}. 2 ist der häufigste Teiler.

Methode 1: Brute-Force-Cracking

Eine Brute-Force-Methode zur Lösung dieses Problems besteht darin, alle Teiler aller Zahlen im Intervall zu finden und sie zusammen mit der Anzahl der Vorkommen in einer Karte zu speichern.

Algorithmus

Prozessdivisor (num)

• Für i = 1 bis n1/2+1

• Wenn num%i == 0

• Wenn num/i == i

• Wenn i nicht in der Karte ist, fügen Sie (i, 1) ein

• Ansonsten Karte[i]++

• Andere

• Wenn i nicht in der Karte ist, fügen Sie (i, 1) ein

• Ansonsten Karte[i]++

• Wenn num/i nicht in der Karte ist, fügen Sie (num/i, 1) ein

• Andere Karten[num/i]++

MaxDivisors (a, b) verarbeiten

• für n = a bis b

• Teiler (n)

• map.erase(1)

• divisor = 1, count = int_min

• Für jedes Element in der Karte

• if it.value > count

• count = it.value

• Divisor = it.key

Beispiel: C++-Implementierung

Im folgenden Programm ermitteln wir den Teiler jeder Zahl in der Funktion divisors() und den maximal auftretenden Teiler in der Funktion 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;
}

Ausgabe

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

Zeitliche Komplexität – O(n3/2), da für jede Zahl im Intervall eine Schleife der Komplexität O(n1/2) durchgeführt wird, um den Teiler zu finden.

Raumkomplexität – O(n), Kartenraum.

Methode 2

Die obige Methode kann weiter optimiert werden, indem die Zeit zum Füllen der Karte bei jedem Auftreten des Divisors verkürzt wird. Anstatt den Teiler jeder Zahl zu ermitteln, können Sie das Vorkommen jedes Teilers im Intervall ermitteln, indem Sie die Unter- und Obergrenze des Intervalls berechnen.

Nehmen wir als Beispiel das Intervall [2, 5].

Die Menge der möglichen Teiler reicht von 1 bis 5. Daher tritt 1 = 5/1 - 2/1 +1 = 4 auf. Es scheint, dass 2 = 5/2 - 2/2 + 1 = 2. Es scheint, dass 3 = 5/3 - 2/3 = 1. Es scheint, dass 4 = 5/4 – 2/4 = 1. Es scheint, dass 5 = 5/5 – 2/5 = 1.

Das Obige kann wie folgt formalisiert werden:

Wenn Untergrenze %-Divisor == 0, dann occ = Obergrenze/Divisor - Untergrenze/Divisor + 1

Other occ = obere Grenze/Divisor – untere Grenze/Divisor

Algorithmus

MaxDivisor (a, b) verarbeiten

• für i = 2 bis b

• Wenn a%i == 0

• Anzahl der Male = b/i - a/i +1

• Andere

• Anzahl der Male = b/i - a/i

• map.insert(i, times)

• divisor = 1, count = int_min

• Für jedes Element in der Karte

• if it.value > count

• count = it.value

• Divisor = it.key

Beispiel: C++-Implementierung

Im folgenden Programm ermitteln wir nicht die Teiler einer Zahl in umgekehrter Reihenfolge, sondern ermitteln für jeden Teiler, wie viele Vielfache er im Intervall hat.

#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;
}

Ausgabe

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

Methode 3

Eine sehr einfache Lösung für dieses Problem wird unten gezeigt,

In jedem Intervall mit einer Größe > 1 hat die Hälfte der Zahlen (jede gerade Zahl) 2 als Teiler.

So kann es wie folgt verwendet werden.

Algorithmus

MaxDivisors (a, b) verarbeiten

• wenn a == b

• ans = a

• Andere

• ans = 2

Beispiel: C++-Implementierung

Im folgenden Programm setzen wir die Beobachtung um, dass jede gerade Zahl 2 als Teiler hat.

#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;
}

Ausgabe

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

Fazit

Kurz gesagt, um den größten vorkommenden Teiler in einem Intervall zu finden, können wir die obige Methode verwenden. Der Zeitbereich reicht von O(n3/2) bis O(1) und der Raumbereich reicht von O(n). zu O( 1).

Das obige ist der detaillierte Inhalt vongrößter gemeinsamer Teiler in einem Intervall. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!