J'ai eu du mal à résoudre Codeforces Round # 592 (Div.2) -C The Football Season avec une équation quadratique linéaire indéfinie, donc dans cet article J'organiserai la solution. De plus, ** ne traite pas de la manière de trouver une solution spéciale par la méthode de division mutuelle d'Euclidienne étendue **, veuillez donc lire l'article de référence 4 pour plus de détails.

(1) Comment résoudre une équation binaire linéaire indéfinie

Cible

Trouver une solution générale pour $ x, y $ dans $ ax + by = c $ ($ a, b, c $: entier)

① Prérequis

** Aucune solution n'existe si $ c $ n'est pas un multiple de $ gcd (a, b) $ **. Inversement, si $ c $ est un multiple de $ gcd (a, b) $, il y aura toujours une solution.

(Ci-après, il s'écrit $ g = gcd (a, b) $.)

② Trouvez une solution spéciale

** Peut être calculé par la méthode de division mutuelle euclidienne étendue **. Voir l'article de référence 4 et le code pour plus de détails. De plus, puisque la solution spéciale de $ ax + by = g $ est obtenue par la méthode de division mutuelle euclidienne étendue, il est nécessaire de multiplier chacune des solutions spéciales obtenues par $ \ frac {c} {g} $ **.

(Ci-après, la solution spéciale obtenue est exprimée par $ x \ _ 0, y \ _ 0 $.)

③ Trouvez une solution générale

Tout d'abord, à partir de $ ax \ _0 + by \ _0 = c $ et $ ax + by = c $, $ a (x-x \ _ 0) + b (y-y \ _0) = 0 $ tient. Ensuite, en remplaçant ** $ a, b $ par $ a ^ {'} = \ frac {a} {g}, b ^ {'} = \ frac {b} {g} $ et en transformant ** , $ A ^ {'} (xx \ _0) = -b ^ {'} (yy \ _0) $.

En raison de la transformation ci-dessus, ** $ a ^ {'} $ et $ b ^ {'} $ sont premiers l'un par rapport à l'autre **, donc $ x-x \ _0 $ doit être un multiple de $ b ^ {'} $. Par conséquent, $ m $ peut être exprimé comme $ x-x \ _0 = m b ^ {'} $ comme un entier. Par conséquent, en remplaçant dans l'équation ci-dessus, la solution générale peut être obtenue comme suit: ** $ x = x \ _ 0 + m b ^ {'}, y = y \ _ 0-m a ^ {'} $ **.

(2) Précautions

Puisque nous multiplions lors de la recherche de la solution spéciale de ax + by = c dans le code C ++, il y a une possibilité de ** débordement **. À ce stade, notez que si $ a, b, c $ ne rentre pas dans l'entier 32 bits, vous devez ** utiliser \ _ \ _ int128 \ _t au lieu de long long ** pour ll [^ 1]. À ce stade, \ _ \ _ int128 \ _t ne peut pas être sorti, donc l'opérateur de sortie doit être défini ou converti en long long. De plus, si $ a, b, c $ ne rentre pas dans un entier 64 bits, veuillez utiliser Python.

(3) Code

J'ai écrit le code dans une structure (Python est une classe). Vous pouvez obtenir une solution générale en appelant simplement le constructeur. De plus, les noms de variables sont conformes à la notation de cet article, veuillez donc les modifier comme il convient.

Je l'ai vérifié dans Codeforces Round # 592 (Div.2) -C The Football Season, mais [^ 2] $ ^, $ [^ 3] Si vous avez des bugs, veuillez nous contacter.

C++

`extgcd.cc`


/*
Équation indéfinie bidimensionnelle du premier ordre(Linear Diophantine equation)
Une fois initialisé, x=x0+m*b,y=y0-m*une solution générale se trouve dans un(m=Initialiser avec 0)
*/
struct LDE{
    ll a,b,c,x0,y0;
    ll m=0;
    bool check=true;//Existe-t-il une solution

    //Initialiser
    LDE(ll a_,ll b_,ll c_): a(a_),b(b_),c(c_){
        //Cast en tant que ll peut être un entier de 128 bits
        ll g=gcd(static_cast<long long>(a),static_cast<long long>(b));
        if(c%g!=0){
            check=false;
        }else{
            //ax+by=Trouver une solution spéciale pour g
            extgcd(a,b,x0,y0);
            //ax+by=Trouver une solution spéciale pour c(Attention au débordement!)
            x0*=c/g;y0*=c/g;
            //Divisez pour trouver une solution générale
            a/=g;b/=g;
        }
    }

    //Méthode de division mutuelle euclidienne étendue
    //Valeur de retour:Engagements maximums pour a et 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;
    }

    //Mettre à jour le paramètre m(Récrire)
    void m_update(ll m_){
        x0+=(m_-m)*b;
        y0-=(m_-m)*a;
        m=m_;
    }
};

Python

Il devrait fondamentalement se comporter de la même manière que C ++.

Cependant, $ x, y $ sont des ** tableaux de longueur 1 contenant des entiers et non **. En effet, vous devez traiter un entier comme un objet mutable pour éviter ** les objets immuables qui deviennent des objets différents lorsque vous essayez de les réécrire dans une fonction **. Pour plus de détails, veuillez lire 1 à 3 de l'article de référence.

`extgcd.py`


'''
Équation indéfinie bidimensionnelle du premier ordre(Linear Diophantine equation)
Une fois initialisé, x=x0+m*b,y=y0-m*une solution générale se trouve dans un(m=Initialiser avec 0)
'''
class LDE:
    #Initialiser
    def __init__(self,a,b,c):
        self.a,self.b,self.c=a,b,c
        self.m,self.x0,self.y0=0,[0],[0]
        #Existe-t-il une solution
        self.check=True
        g=gcd(self.a,self.b)
        if c%g!=0:
            self.check=False
        else:
            #ax+by=Trouver une solution spéciale pour g
            self.extgcd(self.a,self.b,self.x0,self.y0)
            #ax+by=Trouver une solution spéciale pour c
            self.x0=self.x0[0]*c//g
            self.y0=self.y0[0]*c//g
            #Pour trouver une solution générale
            self.a//=g
            self.b//=g

    #Méthode de division mutuelle euclidienne étendue
    #Valeur de retour:Engagements maximums pour a et 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

    #Mettre à jour le paramètre m(Récrire)
    def m_update(self,m):
        self.x0+=(m-self.m)*self.b
        self.y0-=(m-self.m)*self.a
        self.m=m