Es fiel mir schwer, Codeforces Round # 592 (Div.2) -C The Football Season mit einer quadratischen linearen unbestimmten Gleichung zu lösen, also in diesem Artikel Ich werde die Lösung organisieren. Außerdem befasst sich ** nicht mit der Suche nach einer speziellen Lösung durch die Methode der gegenseitigen Teilung des erweiterten Euklidischen **. Lesen Sie daher bitte Referenzartikel 4 für Einzelheiten.
Finden Sie eine allgemeine Lösung für $ x, y $ in $ ax + by = c $ ($ a, b, c $: Ganzzahl)
** Es gibt keine Lösung, wenn $ c $ kein Vielfaches von $ gcd (a, b) $ ist **. Umgekehrt gibt es immer eine Lösung, wenn $ c $ ein Vielfaches von $ gcd (a, b) $ ist.
(Im Folgenden wird es als $ g = gcd (a, b) $ geschrieben.)
** Kann nach der erweiterten euklidischen Methode der gegenseitigen Teilung berechnet werden **. Weitere Informationen finden Sie in Artikel 4 und Code. Da die spezielle Lösung, die durch die erweiterte euklidische Methode der gegenseitigen Teilung erhalten wird, $ ax + mit = g $ ist, ist es notwendig, jede der erhaltenen speziellen Lösungen mit $ \ frac {c} {g} $ ** zu multiplizieren.
(Nachfolgend wird die erhaltene spezielle Lösung ausgedrückt als $ x \ _ 0, y \ _ 0 $.)
Erstens gilt $ a (x-x \ _0) + b (y-y \ _0) = 0 $ von $ ax \ _0 + bis \ _0 = c $ und $ ax + bis = c $. Dann durch Ersetzen von ** $ a, b $ durch $ a ^ {'} = \ frac {a} {g}, b ^ {'} = \ frac {b} {g} $ und Transformieren ** , $ A ^ {'} (xx \ _0) = -b ^ {'} (yy \ _0) $.
Aufgrund der obigen Transformation sind ** $ a ^ {'} $ und $ b ^ {'} $ Primzahlen zueinander **, daher muss $ x-x \ _0 $ ein Vielfaches von $ b ^ {'} $ sein. Daher kann $ m $ als $ x-x \ _0 = m b ^ {'} $ als Ganzzahl ausgedrückt werden. Daher kann durch Einsetzen in die obige Gleichung die allgemeine Lösung erhalten werden als ** $ x = x \ _ 0 + m b ^ {'}, y = y \ _ 0-m a ^ {'} $ **.
Da wir multiplizieren, wenn wir die spezielle Lösung von ax + mit = c im C ++ - Code finden, besteht die Möglichkeit eines ** Überlaufs **. Beachten Sie zu diesem Zeitpunkt, dass Sie, wenn $ a, b, c $ nicht in die 32-Bit-Ganzzahl passen, ** \ _ \ _ int128 \ _t anstelle von long long ** für ll [^ 1] verwenden müssen. Zu diesem Zeitpunkt kann \ _ \ _ int128 \ _t nicht ausgegeben werden, daher muss entweder der Ausgabeoperator definiert oder auf long long umgewandelt werden. Wenn $ a, b, c $ nicht in eine 64-Bit-Ganzzahl passt, verwenden Sie bitte Python.
Ich habe den Code in einer Struktur geschrieben (Python ist eine Klasse). Sie können eine allgemeine Lösung erhalten, indem Sie einfach den Konstruktor aufrufen. Außerdem entsprechen die Variablennamen der Notation in diesem Artikel. Ändern Sie sie daher entsprechend.
Ich habe es in Codeforces Round # 592 (Div.2) -C The Football Season überprüft, aber [^ 2] $ ^, $ [^ 3] Wenn Sie irgendwelche Fehler haben, kontaktieren Sie uns bitte.
C++
extgcd.cc
/*
Zweidimensionale unbestimmte Gleichung erster Ordnung(Linear Diophantine equation)
Bei der Initialisierung wird x=x0+m*b,y=y0-m*Eine allgemeine Lösung findet sich in a(m=Mit 0 initialisieren)
*/
struct LDE{
ll a,b,c,x0,y0;
ll m=0;
bool check=true;//Gibt es eine Lösung?
//Initialisieren
LDE(ll a_,ll b_,ll c_): a(a_),b(b_),c(c_){
//Cast zu lang, solange ll eine 128-Bit-Ganzzahl sein kann
ll g=gcd(static_cast<long long>(a),static_cast<long long>(b));
if(c%g!=0){
check=false;
}else{
//ax+by=Finden Sie eine spezielle Lösung für g
extgcd(a,b,x0,y0);
//ax+by=Finden Sie eine spezielle Lösung für c(Achten Sie auf Überlauf!)
x0*=c/g;y0*=c/g;
//Teilen Sie, um eine allgemeine Lösung zu finden
a/=g;b/=g;
}
}
//Erweiterte euklidische Methode der gegenseitigen Teilung
//Rückgabewert:Maximale Verpflichtungen für a und b
ll extgcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1;
y=0;
return a;
}
ll d=extgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
//Parameter m aktualisieren(Umschreiben)
void m_update(ll m_){
x0+=(m_-m)*b;
y0-=(m_-m)*a;
m=m_;
}
};
Python
Es sollte sich grundsätzlich genauso verhalten wie C ++.
$ X, y $ sind jedoch ** Arrays der Länge 1, die Ganzzahlen enthalten, nicht **. Dies liegt daran, dass Sie eine Ganzzahl als veränderbares Objekt behandeln müssen, um ** unveränderliche Objekte zu vermeiden, die zu unterschiedlichen Objekten werden, wenn Sie versuchen, sie in einer Funktion neu zu schreiben **. Für Details lesen Sie bitte 1 bis 3 des Referenzartikels.
extgcd.py
'''
Zweidimensionale unbestimmte Gleichung erster Ordnung(Linear Diophantine equation)
Bei der Initialisierung wird x=x0+m*b,y=y0-m*Eine allgemeine Lösung findet sich in a(m=Mit 0 initialisieren)
'''
class LDE:
#Initialisieren
def __init__(self,a,b,c):
self.a,self.b,self.c=a,b,c
self.m,self.x0,self.y0=0,[0],[0]
#Gibt es eine Lösung?
self.check=True
g=gcd(self.a,self.b)
if c%g!=0:
self.check=False
else:
#ax+by=Finden Sie eine spezielle Lösung für g
self.extgcd(self.a,self.b,self.x0,self.y0)
#ax+by=Finden Sie eine spezielle Lösung für c
self.x0=self.x0[0]*c//g
self.y0=self.y0[0]*c//g
#Eine allgemeine Lösung finden
self.a//=g
self.b//=g
#Erweiterte euklidische Methode der gegenseitigen Teilung
#Rückgabewert:Maximale Verpflichtungen für a und b
def extgcd(self,a,b,x,y):
if b==0:
x[0],y[0]=1,0
return a
d=self.extgcd(b,a%b,y,x)
y[0]-=(a//b)*x[0]
return d
#Parameter m aktualisieren(Umschreiben)
def m_update(self,m):
self.x0+=(m-self.m)*self.b
self.y0-=(m-self.m)*self.a
self.m=m
ACL Contest 1-B Sum is Multiple → Mein Kommentarartikel
Codeforces Round #592 (Div.2)-C The Football Season → Mein Kommentarartikel
1: Klassifizierungstabelle der integrierten Datentypen von Python (veränderbar usw.) 2: [Ich möchte [Python] unveränderlich als Referenz übergeben 3: Weitergabe per Freigabe und Weitergabe per Referenz 4: Erweiterte euklidische Methode der gegenseitigen Teilung ~ So lösen Sie die lineare unbestimmte Gleichung ax + by = c ~
[^ 1]: Wenn Sie mit Codeforces einreichen, senden Sie mit GNU C ++ 17 (64).
[^ 2]: C ++ senden [^ 3]: Python senden
Recommended Posts