一次合同・CRTで解の類を統合する
概要
一次合同・CRT
一次合同のgcd可解性を判定し、互いに素でない法も含めて複数の剰余類を一つへ統合する。
考え方
合同式で条件を整理するときは、解の整数を一つだけ求めるのではなく、どの間隔で解が現れるかまで持つ。例えば は、整数 を使って と書ける整数全体を表す。このように同じ余りを持つ整数の集合を剰余類と呼ぶ。
まず一次合同を一つの剰余類へ直す。その後、複数の条件を二つずつ統合するのが中国剰余定理(CRT)の使い方である。法が互いに素でなくても、条件が両立すれば一つの剰余類にまとめられる。
一次合同を解いてから二類を統合する
例えば を解きたい。これは が の倍数という条件なので、両辺だけでなく法も で割り、 と同値に変形できる。法 では より の逆元は だから、次を得る。
元の法 で 以上 未満の代表を並べると、解は の二つである。実際、 も も で割った余りが になる。この二つを別々に管理する代わりに、 をまとめて と持てばよい。法を縮めることで、元の法で複数あった解の代表を一つの類で表せる。
一般に、整数 と正の法 に対して を考える。 とすると、 も の倍数も の倍数なので、 が の倍数でなければ解はない。例えば は偶数と奇数が一致しないため解なしとなる。
が を割るときは、 と置く。 が を割る条件は、 が を割る条件と同値である。さらに なので、 なら逆元を使える。
この解の代表を に取ると、全解は ( は任意の整数)である。元の法 での代表は のちょうど 個となる。これで可解条件が十分でもあることと、解を漏らしていないことが分かる。
の場合は、割った後の条件が法 の合同式となるため全整数が解である。逆元は計算せず、 を返す。元の法が の場合や、 かつ が を割る場合もここに含まれる。
互いに素でない二つの条件を統合する
次に、 と を同時に満たす整数を求めよう。一つ目を満たす整数は ( は整数)なので、これを二つ目へ代入する。
ここで使ったのは、先ほどの一次合同の解き方そのものである。 を戻すと だから、統合結果は 。 が両条件を満たすだけでなく、 間隔の全解を表している。法は ではなく、最小公倍数 になる。
二つ目を に替えると、代入後は となる。 は右辺の を割らないので解はない。元の条件でも、一つ目は奇数、二つ目は偶数を要求しており両立しないと確認できる。
一般の二条件 、()でも、 と置けば となる。したがって が差 を割ることが両立の必要十分条件である。これは と同じで、二つの条件が共通の約数に関して矛盾しないかを調べている。
両立するとき、 なら、法 で の逆元を使って を求める。
この右辺を に正規化する。全解 を戻すと、 となる。そこで とし、 を法 で正規化した代表を とすれば、統合結果は である。逆にこの形の整数は両条件を満たすので、解全体がこの一類に一致する。二解の差が 双方の倍数、つまり の倍数になることからも一意性を確認できる。
なら が を割る。両立を確認済みなら、一つ目を満たすすべての整数が二つ目も満たすので、逆元を取らず既存の類 を正規化して返す。例えば に を加えても類は変わらない。同じ法同士の統合もこの場合に含まれ、代表が合同ならその類を返し、合同でなければ両立判定で解なしとなる。
複数条件では全整数の類から始める
初期状態を とすれば、まだ条件のない全整数を表せる。条件を一つ加えるたびに、現在の類と新しい類を上の手順で統合する。「現在の類は、これまでの全条件を満たす整数全体」という意味を保てるため、途中で両立しなければ全体も解なしとなる。
ABC286 F の公式解説では、巡回の移動量から得た複数の余りを CRT で統合する。ABC423 G の公式解説では、桁列の連結から生じる一次合同を、最大公約数による可解判定と法の縮約で解く。問題へ進む際は、まず得られる条件が一次合同なのか、既に余りを指定した類なのかを見分ける。上の数値例と一般 CRT の導出は、本単元で補った説明である。
成立条件と計算量
法は正とし、逆元を取る前に必ず最大公約数による可解判定を行う。一次合同では 、CRT では を先に分岐させる。逆元を取れるのは、縮約した係数と法が互いに素で、法が より大きい場合である。
負の代表も同じ類を表す。例えば は と同じである。各段階の代表は、法を として 以上 未満へ正規化する。負数の % が負になり得る言語では、剰余を求めて負なら を加える。CRT の差 が負になる場合も、この正規化を省かない。
最小公倍数は として、積より先に割り算を行う。ただし、それだけでオーバーフローを防げるわけではない。、代表を作る 、 を求める逆元との積まで収まる整数幅を確認する。最終的な代表が小さくても、途中の積や統合後の法は大きくなり得る。収まらない場合は、より広い整数型・多倍長整数・積を直接作らない剰余乗算などを、必要な箇所に使う。
扱う整数の絶対値と法を上から抑える値を とする。整数の四則演算を定数時間と数える範囲では、最大公約数と逆元を拡張ユークリッドの互除法で求め、一次合同一つ、または二類の統合一回につき時間 。 個の条件の逐次統合は全体で となる。 には入力の法だけでなく、統合で成長する法や途中の整数も含める。反復版の互除法を使い、条件を順に読み込めば、追加空間は 個の整数で済む。多倍長整数を使う場合は、これに桁数に応じた演算時間・記憶量がかかる。
問題一覧
- ABC460 E「x + y ≡ x + y」 公式問題
- ABC286 F「Guess The Number 2」 公式問題
技能・出典
主題: 一次合同・CRTで解の類を統合する(合同条件の可解性を判定し、逆元・一次合同・CRTで解の類を構成できる。)。追加で学ぶ技能: 剰余周期と指数法則を利用する(剰余類上の周期または指数法則を示し、周期状態の前計算や巨大指数の簡約で値を求められる。)。既習技能: 対話protocolを守って情報を取得する(judgeとの問い合わせ応答または交互手番のprotocolを守り、許された形式で応答依存の探索・合法手の提示・終了処理を実行できる。query上限がある場合はその回数も満たす。)。主タグ: 一次合同・CRT、剰余周期・指数法則 / 補助タグ: 対話protocolとquery設計
- ABC423 G「Small Multiple 2」 公式問題
技能・出典
主題: 一次合同・CRTで解の類を統合する(合同条件の可解性を判定し、逆元・一次合同・CRTで解の類を構成できる。)。既習技能: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。)。主タグ: 一次合同・CRT / 補助タグ: 有界全列挙・有限case分解
- ABC245 Ex「Product Modulo 2」 公式問題
技能・出典
主題: 一次合同・CRTで解の類を統合する(合同条件の可解性を判定し、逆元・一次合同・CRTで解の類を構成できる。)。既習技能: 固定線形遷移を巨大回数進める(固定線形遷移を行列または漸化式にし、巨大回数後の値を求められる。) / 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 素因数分解と約数構造(整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。)。主タグ: 一次合同・CRT / 補助タグ: 線形遷移・行列累乗、法上の四則演算・高速累乗・逆元、素因数・約数分解
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC371 G「Lexicographically Smallest Permutation」 公式問題主題: 交換論から選択順を導く
技能・出典
主題: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。追加で学ぶ技能: 一次合同・CRTで解の類を統合する(合同条件の可解性を判定し、逆元・一次合同・CRTで解の類を構成できる。)。既習技能: 関数グラフのcycle・tree分解(後続が一意なグラフをcycleと流入木へ分け、各頂点が属する構造を特定できる。)。主タグ: 貪欲法と交換論、一次合同・CRT / 補助タグ: 関数グラフのcycle・tree分解
前提・学習成果・出典
習得対象の目安: 青色(1600–1999)。一次合同の可解条件を確認し、非互いに素な法も含めてCRTで統合する。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 数論。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-modular-congruence
習得する技能
- 合同条件の可解性を判定し、逆元・一次合同・CRTで解の類を構成できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: gcdと整数解の成立条件、法上の四則演算・高速累乗・逆元。
このUnitを直接前提とする単元: なし。
法上の演算とBézout等式を使えることを前提に、一次合同の可解性を判定して複数条件をCRTで統合する。
このUnitでは扱わないもの
- 可解性判定を要しない通常の法上加減乗除・高速累乗、および剰余周期だけの利用。