■

一次不定方程式周りのあれこれ

競プロの文脈で一次不定方程式を解くのはだいたい次の2パターンのどちらかかと思います

  1. ax+by=cを満たす最小の非負整数xを出力
  2. K\equiv p \pmod a , K\equiv q \pmod bを満たす最小の非負整数Kを出力

基本的に1はextGCD,2はCRTで解いていくのが一般的らしいです

  • 1をextGCDで解く場合
    まず解が存在するかを確認します　具体的にはc%gcd(a,b)=0ならば解が存在します　同時にa,b,cをgcd(a,b)で割っておく必要があります(最小解が求まらない)　あとは簡単で、extGCDのライブラリにほいすれば良いです
    xの復元がやや面倒です　まずextGCDによって得られたxは ax+by=1を満たすxの一つ(非負とは限らない)です　そのためxをc倍します　ここで多くの場合ではオーバーフローをケアしなくていいようです(なぜならextGCDでもとまる解は小さいからです(wikipediaのベズーの等式より))
    さらに最小の非負整数にするため、xを((x%b)+b)%bに置き換えます　これはxが負であったりしても大丈夫なので嬉しいですね　xを答えて終わりです

  • 2をCRTで解く場合
    ライブラリに入れて終わりです　解がない場合だけ注意です

1と2はよく似た問題なので、互いに入れ替えることができます(両方のライブラリを持ってるなら入れ替える必要は当然ないです)

  • 2->1:2の二式をいじると、適当にx,yをとって、ax+p=K,by+q=Kとすることができるので、二式を連立すると1の形になります これをextGCDで解くとxが求まります 2の問題では最小のKが欲しいので、xからKを復元する必要があります ここで注意するのはextGCDを解く際にa/=gcd(a,b)をしている場合、ax+p=Kとすると壊れることです extGCDで1を解いた時に得られるxはax+p=Kという式を満たす最小のxなのですが、この時の係数aはgcdで割る前のものだからです 気をつけましょう

  • 1->2:1を立式する直前にすでに2の形になってることが多そうですが……　上の逆操作みたいにやればいいです ax=K,-by+c=Kを満たすような最小のKを求めます CRTするときに、 K\equiv 0 \pmod a , K\equiv c \pmod bとなるので、Kを求めたら素直にaで割ってxを得ることができます　この場合は大丈夫ですが、yを求めたい時に(K-c)/(-b)をやるとK>cの時にyが負になって悲しくなります　そういう時はKからlcm(a,b)を足したり引いたりしてがんばりましょう(だいたいCRTの帰り値に含まれてそう)

あとはax+by=cではなくax-by=cとかax+by=-cみたいなのだと嫌な気持ちになりますが、基本的にはそのままやって大丈夫です(ax-by=c->ax+(-b)y+cと置き換えれば良い)

練習問題　ネタバレを防ごうと思いましたが面倒なので番号だけおいておきます

  • ABC186-E 1の典型です
  • ABC193-E 2の典型です
  • ACL1-B ちょっと大変
  • yukicoder-No.1364　普通に大変
  • yukicoder-No.1287　いい問題だと思います

なんかあれば教えてください(追記修正はします)