ABC 444 G — Kyoen

考察

円周条件をu=Cx−A,v=Cy−Bと置くと、u²+v²=Nかつ(u,v)≡(−A,−B) mod Cとなる。N自体は巨大だが素因数分解が与えられるため、ガウス整数g=u+viのnorm g共役g=Nから、各素因数をgへどう分配するか考える。

q≡3 (mod 4)はガウス整数でも素数なので、その指数が奇数なら解は0。偶数ならq^{e_q/2}を実因子として固定する。2には(1+i)^{e_2}を固定する。p≡1 (mod 4)ではp=a²+b²=π共役πと表せるので、gに入る部分はπ^{e−k}共役π^k、0≤k≤e。この分配と単元1,i,−1,−iを選べばnorm Nのガウス整数を一意に尽くす。p≤100なのでa,bは整数の全探索で見つけられる。

指数e≤10^18の分配を一つずつ試すのは不可能。R=(Z/CZ)[i]のC²個の座標上で冪列v_t=π^tを作る。v_0=(1,0)、v_{t+1}=v_tπと、現在の値から次を決められる列なので、初めて再出現した値から前周期μと周期τを得られる。μ+τ≤C²であり、指数j≥μではv_j=v_{μ+(j−μ) mod τ}をO(1)で参照できる。πが可逆とは限らず、指数分配列そのものを関数グラフとはみなさない。

分配の前半0≤k≤h=⌊e/2⌋ではz_k=p^k π^{e−2k}を計算し、後半は共役で戻す。π^{μ+τ}=π^μのnormを取るとp^{μ+τ}=p^μも成立する。したがってp^kの冪列もk≥μで周期τを使え、中央の範囲

μ≤k≤⌊(e−μ)/2⌋

ではz_{k+τ}=z_k。両方の指数が前周期を抜けた範囲だからである。先頭のk<μと末尾のe−2k<μは別々に高々O(C²)項を直接計算する。二範囲が重なる場合は和集合を一度だけ処理し、中央が空なら周期集計しない。

中央は最初の高々τ項を計算し、同じk mod τの項数を1+⌊(最後−k)/τ⌋で剰余分布へ加える。例えばC=p=5,π=1+2i,e=4では全分配は(3,1),(0,0),(0,0),(0,0),(3,4)。途中の(0,0)の再出現から周期が続くと判断すると最後を落とすが、前後の非周期部分を分ければ正しく数えられる。

前半の分布H[a,b]から全分配分布D[a,b]=H[a,b]+H[a,−b]を作る。eが偶数なら中央k=e/2のp^{e/2}をこの式で二度加えているため一個分を引く。他の指数分配が同じ剰余になる場合は、その個数を保つ。

固定因子g0=(1+i)^{e_2}Π_{q≡3 mod4}q^{e_q/2}を法Cで高速累乗し、F[g0]=1から始める。素因数ごとのDを順に合成する。座標r=(a,b),s=(c,d)の積はr*s=(ac−bd,ad+bc) mod Cなので、Fnew[r*s]+=F[r]D[s]を全C²×C²組で行う。最後に単元4通りで回転した分布を足し、(−A mod C,−B mod C)を照会する。法998244353上で個数を持ち、同じ剰余へ写った単元も重複削除しない。

典型の発動条件

巨大な指数分配を単独の冪列へ分解する

発動条件: 小さな有限環で巨大な指数を扱うが、逆元を仮定できないとき。

冪列の前周期と周期を求める。指数分配の両側が前周期を抜ける中央だけを周期集計し、端を直接計算する。

剰余分布の乗法合成

発動条件: 独立な因子の選び方が、最終的には積の小さな剰余状態だけに影響するとき。

積の座標式から分布を合成する。同じ剰余でも元の選び方が違えば個数を足す。

問題固有の要素

p≡3 (mod 4) とp≡1 (mod 4) の合同類を区別する。座標の符号と順序を持つ解を数えるため、単元4通りを維持する。

正当性

norm Nのガウス整数は、q≡3 mod4の偶指数の固定因子、2の固定因子、p≡1 mod4の全指数分配と四単元で一意に表される。単独のπの冪列は決定的な乗法遷移なので前周期μと周期τを持ち、そのnormのpの冪列も同じμ,τを使える。k≥μかつe−2k≥μの範囲でのみ分配列の周期τを利用し、両端は直接計算するため全前半を正確に数える。共役で後半を戻し、偶指数の中央だけ一個引くと全e+1分配を数える。座標乗算に従う分布合成と四単元の加算で全表現の剰余頻度を得る。指定合同条件を満たす(u,v)と整数点x=(u+A)/C,y=(v+B)/Cは一対一なので、照会した頻度が答えである。

実装上の注意

  • πの逆元を使わない。両端は冪列参照または高速累乗、中央だけ周期頻度を使う。
  • eが偶数の中央を一度だけ数える。C=1でも四単元と各指数分配は異なる整数表現として数える。
  • 個数・頻度の演算は998244353、座標の演算はC。最後の照会は(−A mod C,−B mod C)。

復習の核

  • 有限集合上の列が周期化する根拠は「現在状態から次が決まる」ことである。二つの指数が逆方向に動く列にはそのまま適用しない。
  • 圧縮した剰余状態が同じでも、指数分配や単元の選び方の個数を保つ。

計算量と制約

時間

O(sC^4+sC² log Emax+s√Pmax)。sは与えられた素因数数、Pmax≤100。冪列の周期検出O(C²)、両端・中央の代表計算を高速累乗してO(C² log Emax)、分布合成が各O(C^4)。πの構成は各O(√Pmax)。

空間

O(C²)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: N \geq 1; 2 \leq P_i \leq 100; P_i are distinct primes.; 1 \leq E_i \leq 10^{18}; 1 \leq C \leq 50; 0 \leq A,B \lt C; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Kyoen の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: Gaussian整数・二平方和

主題
  • Gaussian整数・二平方和: Z[i]での素因数分解と共役を用い、整数の二平方和表現をprime exponentごとに構成・数え上げる。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: Gaussian整数・二平方和

    補助タグ: 関数グラフのcycle・tree分解

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: Gaussian整数・二平方和

    • Z[i]での素因数分解と共役を用い、整数の二平方和表現をprime exponentごとに構成・数え上げる。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    • 関数グラフのcycle・tree分解 — 状態グラフのモデリングと探索で得た考え方と実装を再利用し、関数グラフのcycle・tree分解の発動条件・正当化・境界を重複なく学ぶ。
    • 素因数分解と約数構造 — 初歩的な素因数分解を、指数vectorと約数格子へ条件を分解する道具として発展させる。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題