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.

(1) Wie man eine binäre lineare unbestimmte Gleichung löst

Ziel

Finden Sie eine allgemeine Lösung für $ x, y $ in $ ax + by = c $ ($ a, b, c $: Ganzzahl)

① Voraussetzungen

** 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.)

② Finden Sie eine spezielle Lösung

** 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 $.)

③ Finden Sie eine allgemeine Lösung

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 ^ {'} $ **.

(2) Vorsichtsmaßnahmen

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.

(3) Code

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