競プロのライブラリ整理~二元一次不定方程式~



[Codeforces Round #592 (Div.2)-C The Football Season](https://codeforces.com/contest/1244/problem/C)を二元一次不定方程式で解く際に苦労したので、この記事で解法を整理していこうと思います。また、**拡張ユークリッドの互除法による特殊解の求め方は扱わない**ので、詳しくは参考記事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](https://codeforces.com/contest/1244/problem/C)においてverifyしましたが[^2]$^,$[^3]、バグがあればご連絡ください[^4]。

## C++

```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を読んでください。

```python: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)二元一次不定方程式を使う問題

- [ACL Contest 1-B Sum is Multiple](https://qiita.com/DaikiSuyama/items/c2639a53c457439198b9#b%E5%95%8F%E9%A1%8C)
- [Codeforces Round #592 (Div.2)-C The Football Season](https://codeforces.com/contest/1244/problem/C)

# (5)参考記事

1. [Pythonの組み込みデータ型の分類表（ミュータブル等）](https://gammasoft.jp/blog/python-built-in-types/#immutable)
2. [【python】immutableを参照渡ししたい](https://www.haya-programming.com/entry/2016/12/27/025039)
3. [共有渡しと参照の値渡しと](https://www.haya-programming.com/entry/2018/06/19/181657)
4. [拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜](https://qiita.com/drken/items/b97ff231e43bce50199a)

[^1]: Codeforcesで提出する際にはGNU C++17 (64)で提出しましょう。
[^2]: [C++の提出](https://codeforces.com/contest/1244/submission/97621882)
[^3]: [Pythonの提出](https://codeforces.com/contest/1244/submission/97620779)
[^4]: [ABC186E - Throne](https://atcoder.jp/contests/abc186/tasks/abc186_e)で拡張ユークリッド互助法がバグったので書き換えました。