Finden Sie den größten gemeinsamen Teiler in einem bestimmten Bereich

Das Problem besagt, dass wir den GCD in einem bestimmten Bereich finden müssen. Wir erhalten zwei positive ganze Zahlen x und y und zwei ganze Zahlen p und q im Bereich [p,q]. Wir müssen den GCD (größten gemeinsamen Teiler) der Zahlen x und y finden, die in den Bereich [p,q] fallen. GCD, in der Mathematik als größter gemeinsamer Teiler bekannt, ist die größte positive ganze Zahl, die zwei gegebene positive ganze Zahlen teilt. Die angegebene Ganzzahl darf nicht Null sein. Für zwei beliebige positive ganze Zahlen x und y wird es als ggT(x,y) ausgedrückt.

Zum Beispiel haben wir zwei positive ganze Zahlen 6 und 9. Der größte gemeinsame Teiler gcd(6,9) ist 3, da es die größte Zahl ist, die diese beiden Zahlen teilt.

Aber bei diesem Problem müssen wir den größten gemeinsamen Teiler zweier gegebener positiver Ganzzahlen innerhalb eines bestimmten Bereichs finden. Lassen Sie uns dieses Problem anhand eines Beispiels verstehen. Wir erhalten 4 Zahlen als Eingabe x und y, um den gcd dieser Zahlen zu ermitteln, und zwei Zahlen, die den Bereich des gcd angeben, d. h. [p, q].

Eingabe: x=8, y=12, p=1, q=3

Ausgabe: 2

Erklärung - Da der größte gemeinsame Teiler der beiden gegebenen Zahlen x und y 4 ist. Aber 4 liegt nicht im Bereich [1,3]. Der größte gemeinsame Teiler im Bereich [1,3] ist 2, was unsere gewünschte Ausgabe ist.

Eingabe: x=17, y=15, a=5, b=10

Ausgabe: -1

Erklärung - Der größte gemeinsame Teiler der Zahlen 17 und 15 ist 1. Weil 1 nicht im angegebenen Bereich liegt [5,10]. Wenn es im angegebenen Bereich keinen gemeinsamen Teiler gibt, müssen wir -1 als Ausgabe ausgeben.

Algorithmus

Der Algorithmus, den wir zur Lösung des Problems verwenden, ist sehr einfach und mathematisch verwandt. Zuerst ermitteln wir den ggT (größter gemeinsamer Teiler) der Zahlen x und y. In C++ gibt es eine integrierte Funktion namens gcd(), die den größten gemeinsamen Teiler von Zahlen als Ausgabe zurückgibt.

Grammatik

int divisor=gcd(x,y);

Wir können auch die effiziente Methode des Euklidischen Algorithmus verwenden, um den ggT zweier Zahlen zu ermitteln. Beide arbeiten gleichzeitig und die Zeitkomplexität beträgt O(log(min(x,y)).

Nun können wir einfache Gesetze der Arithmetik verwenden, um zu dem Schluss zu kommen, dass eine Zahl, die den ggT zweier Zahlen teilt, auch durch die beiden Zahlen selbst geteilt wird . Wenn wir also in einer for-Schleife von i=1 nach sqrt(gcd(x,y)) iterieren, können wir alle gemeinsamen Teiler der Zahl ermitteln.

Überprüfen Sie dann, ob jedes i bis sqrt(gcd(x,y)) i gcd(x,y) teilt. Wenn i gcd(x,y) teilt, können wir sagen, dass gcd(x,y)/i auch der Teiler von gcd ist, woraus wir schließen, dass es auch der gemeinsame Teiler der Zahlen x und y ist.

Lassen Sie uns dieses Konzept anhand eines Beispiels verstehen. Angenommen, x und y sind 32 bzw. 48. gcd(18,27) ist 16. In diesem Fall iterieren wir also von i=1 bis i<=4, was sqrt(16) ist. Betrachten wir i=2. Hier dividiere ich durch gcd(18,27), was 16/2 ist, was 8 entspricht. Daher dividiert gcd(x,y)/i auch gcd(x,y), um i zu erhalten. <=4，即 sqrt(16)。让我们考虑 i=2。这里我除以 gcd(18,27)，即 16/2，等于 8。因此 gcd(x,y)/i 也会除 gcd(x,y) 得到 i。

Hinweis – Wenn die Zahl n durch eine beliebige Zahl x geteilt wird, um y zu erhalten, was als $frac{n}{x}:=:y$ ausgedrückt werden kann, dann teilt y n durch x $(x:times: y:=: n)$.

Dieser Algorithmus ist wahrscheinlich der effizienteste Weg, dieses Problem zu lösen. Während wir diesem Algorithmus folgen, prüfen wir ständig, ob der gemeinsame Nenner im Bereich [a,b] liegt. Wenn nicht, verwenden wir die Funktion max(), um den Teiler in der Variablen kontinuierlich zu aktualisieren, um den größten gemeinsamen Teiler im Bereich zu erhalten.

max()-Funktionssyntax

int m = max(a,b);

Es gibt den Maximalwert von a und b zurück.

Methode

Hier ist der Ansatz, den wir verfolgen werden –

• Initialisieren Sie eine Funktion, um den größten gemeinsamen Teiler innerhalb eines bestimmten Bereichs zu berechnen.

• Berechnen Sie den ggT zweier gegebener positiver Zahlen x und y.

• Variablennamen initialisieren ans = -1.

• Iteriere von i=1 bis i<=sqrt(gcd(x,y)) in der for-Schleife und überprüfe weiterhin, ob i gcd(x,y) teilt. <=sqrt(gcd(x,y)) 并不断检查 i 是否整除 gcd(x,y)。

• Wenn (gcd(x,y)%i)=0, prüfen Sie, ob i im Bereich [a,b] liegt und verwenden Sie die Funktion max(), um es in ans zu speichern, sodass wir den größten gemeinsamen Teiler erhalten, der bei liegt innerhalb des Bereichs.

• Überprüfen Sie auch, ob gcd/i innerhalb des Bereichs liegt. Wenn es innerhalb des Bereichs liegt, verwenden Sie die Funktion max() erneut, um den Wert von ans zu aktualisieren.

• Gib ans zurück, nachdem alle Iterationen in der for-Schleife abgeschlossen wurden.

Beispiel

Implementierung dieser Methode in C++ -

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

// to calculate gcd of two numbers using Euclidean algorithm
int gcd(int a, int b){
   if(a == 0)
   return b;
   return gcd(b % a, a);
}

//function to calculate greatest common divisor in the given range [a,b]
int build(int x, int y, int a, int b) {

   //using C++ inbuilt library to calculate gcd of given numbers
   int z = gcd(x, y); //we can use euclidean algorithm too as an alternative
   int ans = -1; //storing -1 for the case when no common divisor lies in the range
   for(int i = 1; i<=sqrt(z); i++) { //iterating until sqrt(z) because either of two factors
      //of a number must be less than square root of the number
      if(z % i == 0) {
         if(i >= a && i <= b) //checking it i lies in the range
         ans = max(ans, i); //storing maximum value
         if((z / i) >= a && (z / i) <= b)
         ans = max(ans, z / i);
      }
   }
   return ans;
}
int main() {
   int x, y, a, b;
   x=24, y=42, a=3, b=9;
   cout << build(x, y, a, b) <<" is the gcd that lies in range ["<<a<<","<<b<<"]"<<endl;
   return 0;
}

Ausgabe

6 is the gcd that lies in range [3,9]

Zeitkomplexität: O(log(min(x,y)) + sqrt(z)), wobei z der größte gemeinsame Teiler zweier Zahlen x und y ist.

Raumkomplexität: O(1), weil kein zusätzlicher Raum verwendet wird.

Fazit

Wir haben Möglichkeiten besprochen, das gcd-Problem für zwei Zahlen im Bereich [a,b] zu lösen. So können wir das obige Problem in C++ mit verschiedenen Funktionen lösen.

Ich hoffe, dass Sie diesen Artikel hilfreich fanden und alle Ihre Konzepte zu diesem Problem geklärt haben.

Das obige ist der detaillierte Inhalt vonFinden Sie den größten gemeinsamen Teiler in einem bestimmten Bereich. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!