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.
Find a general solution for $ x, y $ in $ ax + by = c $ ($ a, b, c $: integer)
** 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) $.)
** 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 $.)
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 ^ {'} $ **.
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.
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
ACL Contest 1-B Sum is Multiple → My commentary article
Codeforces Round #592 (Div.2)-C The Football Season → My commentary article
1: Python built-in data type classification table (mutable, etc.) 2: [I want to pass [python] immutable by reference 3: Passing by value and passing by reference 4: Extended Euclidean algorithm ~ How to solve the linear indefinite equation ax + by = c ~
[^ 1]: When submitting with Codeforces, submit with GNU C ++ 17 (64).
[^ 2]: Submit C ++ [^ 3]: Python submission
Recommended Posts