Codeforces Round #592 (Div.2)-C The Football Seasonを二元一次不定方程式で解く際に苦労したので、この記事で解法を整理していこうと思います。また、拡張ユークリッドの互除法による特殊解の求め方は扱わないので、詳しくは参考記事4を読んでください。

#(1)二元一次不定方程式の解き方

##目標

$ax+by=c$ ($a,b,c$:整数)における$x,y$の一般解を求める

###①前提条件

$c$が$gcd(a,b)$の倍数でない場合は解が存在しません。逆に$c$が$gcd(a,b)$の倍数の場合は必ず解が存在します。

(↓以下では、$g=gcd(a,b)$として表記します。)

###②特殊解を求める

拡張ユークリッドの互除法により求めることができます。詳しくは参考記事4とコードを見てください。また、拡張ユークリッドの互除法により求まるのは$ax+by=g$の特殊解なので、求まった特殊解をそれぞれ$\frac{c}{g}$倍する必要があります。ここで、拡張ユークリッドの互助法を行うには$a>0,b>0$であることが必要です。

(↓以下では、求まった特殊解を$x_0,y_0$として表記します。)

###③一般解を求める

まず、$ax_0+by_0=c$かつ$ax+by=c$より、$a(x-x_0)+b(y-y_0)=0$が成り立ちます。そして、$a,b$を$a^{'}=\frac{a}{g},b^{'}=\frac{b}{g}$に置き換えて変形することで、$a^{'}(x-x_0)=-b^{'}(y-y_0)$になります。

前述の変形により**$a^{'}$と$b^{'}$は互いに素なので、$x-x_0$は$b^{'}$の倍数であることが必要です。よって、$m$を整数として$x-x_0=m b^{'}$として表すことができます。したがって、先ほどの式に代入すれば、$x=x_0+m b^{'},y=y_0-m a^{'}$として一般解が求まります**。

#(2)C++での注意点

$a,b,c$が32bit整数の場合はllには64bit整数を使うようにしてください。$a,b,c$が32bit整数に収まらない場合はPythonを使うようにしてください。

#(3)コード

構造体(Pythonはクラス)でコードを書きました。コンストラクタを呼ぶだけで一般解を求められます。また、変数名はこの記事の表記に準拠しているので、適宜変えて使ってください。

Codeforces Round #592 (Div.2)-C The Football Seasonにおいてverifyしましたが¹$^,$²、バグがあればご連絡ください³。

C++

extgcd.cc

/*
二元一次不定方程式 ax+by=c(a≠0かつb≠0) を解く
初期化すると、x=x0+m*b,y=y0-m*aで一般解が求められる(m=0で初期化)
llは32bit整数まで→超えたらPythonに切り替え
*/
struct LDE{
    ll a,b,c,x,y;
    ll m=0;
    bool check=true;//解が存在するか

    //初期化
    LDE(ll a_,ll b_,ll c_): a(a_),b(b_),c(c_){
        ll g=gcd(a,b);
        if(c%g!=0){
            check=false;
        }else{
            //ax+by=gの特殊解を求める
            extgcd(abs(a),abs(b),x,y);
            if(a<0)x=-x;
            if(b<0)y=-y;
            //ax+by=cの特殊解を求める(オーバフローに注意！)
            x*=c/g;y*=c/g;
            //一般解を求めるために割る
            a/=g;b/=g; 
        }
    }

    //拡張ユークリッドの互除法
    //返り値:aとbの最大公約数
    ll extgcd(ll a,ll b,ll &x0,ll &y0){
        if(b==0){
            x0=1;
            y0=0;
            return a;
        }
        ll d=extgcd(b,a%b,y0,x0);
        y0-=a/b*x0;
        return d;
    }

    //パラメータmの更新(書き換え)
    void m_update(ll m_){
        x+=(m_-m)*b;
        y-=(m_-m)*a;
        m=m_;
    }
};

Python

基本的にはC++と同じ挙動をするようにしてあるはずです。

ただし、$x,y$は整数ではなく整数を格納した長さ1の配列です。これは整数(イミュータブルなオブジェクト)を関数内で書き換えようとすると別のオブジェクトになることを避けるために、ミュータブルなオブジェクトとして整数を扱う必要があるからです。詳しくは参考記事の1~3を読んでください。

extgcd.py

'''
二元一次不定方程式 ax+by=c(a≠0かつb≠0) を解く
初期化すると、x=x0+m*b,y=y0-m*aで一般解が求められる(m=0で初期化)
'''
from math import gcd
class LDE:
    #初期化
    def __init__(self,a,b,c):
        self.a,self.b,self.c=a,b,c
        self.m,self.x,self.y=0,[0],[0]
        #解が存在するか
        self.check=True
        g=gcd(self.a,self.b)
        if c%g!=0:
            self.check=False
        else:
            #ax+by=gの特殊解を求める
            self.extgcd(abs(self.a),abs(self.b),self.x,self.y)
            if a<0:self.x[0]=-self.x[0]
            if b<0:self.y[0]=-self.y[0]
            #ax+by=cの特殊解を求める
            self.x=self.x[0]*c//g
            self.y=self.y[0]*c//g
            #一般解を求めるために
            self.a//=g
            self.b//=g

    #拡張ユークリッドの互除法
    #返り値:aとbの最大公約数
    def extgcd(self,a,b,x0,y0):
        if b==0:
            x0[0],y0[0]=1,0
            return a
        d=self.extgcd(b,a%b,y0,x0)
        y0[0]-=(a//b)*x0[0]
        return d

    #パラメータmの更新(書き換え)
    def m_update(self,m):
        self.x+=(m-self.m)*self.b
        self.y-=(m-self.m)*self.a
        self.m=m

#(4)二元一次不定方程式を使う問題

(5)参考記事

C++の提出 ↩
Pythonの提出 ↩
ABC186E - Throneで拡張ユークリッド互助法がバグったので書き換えました。 ↩