gcd不変量・差分構造

概要

差・周期・range条件に共通するgcd不変量を抽出し、共通因子や剰余classを分離する。

考え方

gcdは整数の共通因子を最大公約数へ集める。加減算でgcdが保存されるため、全体のgcdや隣接差のgcdへ問題を直せる場合がある。

整数a,bの共通約数はaとb−qaの共通約数に一致するので、gcd(a,b)=gcd(a,b−qa)。Euclidの除算はこの不変量を保ち、非負の余りを小さくして終了する。配列全体へ同じxを加えたときは、各要素から先頭を引くことでgcd(a_0+x,…,a_(N−1)+x)=gcd(a_0+x,a_1−a_0,…,a_(N−1)−a_0)。右辺の差のgcdを一度求めれば、xごとのqueryは先頭とのgcd一回になる。N=1では差集合のgcdを0としてよい。

さらに、全要素が同じ剰余rになる法m>0は、全ての差を割ることと同値である。差のgcdをgとすれば候補mはgの正の約数へ絞れるが、g=0なら全要素が同じなので任意の正のmがこの条件を満たす。この境界を「0の約数一覧」で処理しない。

静的な一要素除外にはP[0]=S[N]=0、P[i+1]=gcd(P[i],a_i)、S[i]=gcd(a_i,S[i+1])を作り、iを除く答えをgcd(P[i],S[i+1])とする。互いに素な要素も0も同じ式で扱える。一方、区間gcdは和のようにprefix同士を引いて取り出せず、動的なrange条件にはgcdの結合性を使う区間集約が要る。

成立条件と計算量

EuclidはO(log U)回の除算。配列のgcd集約はO(N log U)の上界となる。gcd(0,a)=|a|を使い、全て0の境界を扱う。最小公倍数は先にgcdで割ってから掛け、overflowを確認する。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。差や周期をgcdにまとめ、共通因子と剰余類が保存する条件を示す。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 数論。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-gcd-structure

gcd不変量・差分構造

習得する技能

  • gcd不変量によって共通因子・差分・周期成分を分離し、rangeまたは剰余類ごとの問いを処理できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: 有向walkの周期・cycle差分gcd、Stern–Brocot木の経路と祖先。

差・周期・range条件に共通するgcd不変量を抽出し、共通因子や剰余classを分離する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

このUnitでは扱わないもの

  • Bézout係数を求めて一次不定方程式の具体解・一般解を構成する手順は「gcdと整数解の成立条件」で扱う。gcdによる必要条件や剰余類への分解と、解を実際に構成する技能を区別する。

根拠