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

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$の特殊解