I had a hard time solving Codeforces Round # 592 (Div.2)-C The Football Season with a quadratic linear indefinite equation, so in this article I will organize the solution. Also, ** does not deal with how to find a special solution by the extended Euclidean algorithm **, so please read Reference Article 4 for details.

(1) How to solve the two-dimensional first-order indefinite equation

Target

Find a general solution for $ x, y $ in $ ax + by = c $ ($ a, b, c $: integer)

① Prerequisites

** No solution exists if $ c $ is not a multiple of $ gcd (a, b) $ **. Conversely, if $ c $ is a multiple of $ gcd (a, b) $, there will always be a solution.

(Hereafter, it is written as $ g = gcd (a, b) $.)

② Find a special solution

** Can be calculated by the extended Euclidean algorithm **. See reference article 4 and code for more details. Also, since the extended Euclidean algorithm gives a special solution of $ ax + by = g $, it is necessary to multiply each of the obtained special solutions by $ \ frac {c} {g} $ **.

(Hereafter, the obtained special solution is expressed as $ x \ _ 0, y \ _ 0 $.)

③ Find a general solution

First, from $ ax \ _0 + by \ _0 = c $ and $ ax + by = c $, $ a (x-x \ _0) + b (y-y \ _0) = 0 $ holds. Then, by replacing ** $ a, b $ with $ a ^ {'} = \ frac {a} {g}, b ^ {'} = \ frac {b} {g} $ and transforming ** , $ A ^ {'} (xx \ _0) =-b ^ {'} (yy \ _0) $.

Due to the above transformation, ** $ a ^ {'} $ and $ b ^ {'} $ are relatively prime **, so $ x-x \ _ 0 $ must be a multiple of $ b ^ {'} $. Therefore, $ m $ can be expressed as $ x-x \ _0 = m b ^ {'} $ as an integer. Therefore, by substituting it into the above formula, the general solution can be obtained as ** $ x = x \ _ 0 + m b ^ {'}, y = y \ _ 0-m a ^ {'} $ **.

(2) Precautions

Since multiplication is performed when finding a special solution of ax + by = c in C ++ code, there is a possibility of ** overflow **. At this time, if $ a, b, c $ do not fit in a 32-bit integer, ** ll should use \ _ \ _ int128 \ _t instead of long long ** [^ 1]. At this time, \ _ \ _ int128 \ _t cannot be output, so either the output operator must be defined or cast to long long. Also, if $ a, b, c $ does not fit in a 64-bit integer, please use Python.

(3) Code

I wrote the code in a struct (Python is a class). You can find the general solution just by calling the constructor. Also, the variable names conform to the notation in this article, so please change them as appropriate.

I verified it in Codeforces Round # 592 (Div.2)-C The Football Season, but [^ 2] $ ^, $ [^ 3] If you have any bugs, please contact us.

C++

`extgcd.cc`


/*
Two-dimensional first-order indefinite equation(Linear Diophantine equation)
When initialized, x=x0+m*b,y=y0-m*a general solution is found in a(m=Initialize with 0)
*/
struct LDE{
    ll a,b,c,x0,y0;
    ll m=0;
    bool check=true;//Does a solution exist

    //Initialize
    LDE(ll a_,ll b_,ll c_): a(a_),b(b_),c(c_){
        //Cast to long long as ll may be a 128bit integer
        ll g=gcd(static_cast<long long>(a),static_cast<long long>(b));
        if(c%g!=0){
            check=false;
        }else{
            //ax+by=Find a special solution for g
            extgcd(a,b,x0,y0);
            //ax+by=Find a special solution for c(Be careful of overflow!)
            x0*=c/g;y0*=c/g;
            //Divide to find a general solution
            a/=g;b/=g;
        }
    }

    //Extended Euclidean algorithm
    //Return value:Greatest common divisor of a and 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;
    }

    //Update parameter m(Rewrite)
    void m_update(ll m_){
        x0+=(m_-m)*b;
        y0-=(m_-m)*a;
        m=m_;
    }
};

Python

It should basically behave the same as C ++.

However, $ x, y $ are ** arrays of length 1 containing integers, not integers **. This is because you need to treat an integer as a mutable object to avoid ** immutable objects that become different objects when you try to rewrite them in a function **. For details, please read 1 to 3 of the reference article.

`extgcd.py`


'''
Two-dimensional first-order indefinite equation(Linear Diophantine equation)
When initialized, x=x0+m*b,y=y0-m*a general solution is found in a(m=Initialize with 0)
'''
class LDE:
    #Initialize
    def __init__(self,a,b,c):
        self.a,self.b,self.c=a,b,c
        self.m,self.x0,self.y0=0,[0],[0]
        #Does a solution exist
        self.check=True
        g=gcd(self.a,self.b)
        if c%g!=0:
            self.check=False
        else:
            #ax+by=Find a special solution for g
            self.extgcd(self.a,self.b,self.x0,self.y0)
            #ax+by=Find a special solution for c
            self.x0=self.x0[0]*c//g
            self.y0=self.y0[0]*c//g
            #To find a general solution
            self.a//=g
            self.b//=g

    #Extended Euclidean algorithm
    #Return value:Greatest common divisor of a and 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

    #Update parameter m(Rewrite)
    def m_update(self,m):
        self.x0+=(m-self.m)*self.b
        self.y0-=(m-self.m)*self.a
        self.m=m