ABC 335 G — Discrete Logarithm Problems

考察

mod prime Pの非零元は位数P-1の巡回群をなし、A_iの冪で到達できる集合はA_iが生成する部分群である。したがってA_jへ到達可能であることはord(A_j)がord(A_i)を割ることと同値になる。

採用する候補: 各A_iの位数を求め、約数lattice上の頻度zeta変換で整除pairを数える

離散対数そのものを求めず、部分群包含を位数の整除へ落として全pairを約数数に依存する計算へ圧縮できる。

棄却する候補: 各(i,j)についてdiscrete logarithmを解く

N^2 pairがあり、各pairの離散対数も高価で制約に全く合わない。

P-1を素因数分解しM=P-1から、素因数qごとにA_i^(M/q)≡1の間Mをqで割ると最小位数が得られる。ord(A_j)|ord(A_i)なら巡回群の一意な同位数部分群の包含により正の冪kが存在する。

P-1をtrial divisionで素因数分解する。各A_iについてmodular exponentiationで位数を削減し、その素因数指数vectorの頻度を数える。mixed-radix配列上で各軸のprefix zeta変換を行って各dに対するΣ_{e|d}freq[e]を得て、Σ_d freq[d]·divisorCount[d]を出力する。

典型の発動条件

有限巡回群の位数

発動条件: 冪到達可能性が乗法群内の生成部分群への所属で決まる。

各値を具体的な離散logでなくelement orderへ写し、部分群包含を整除判定にする。

約数latticeの高速zeta変換

発動条件: 全orderが一つの整数P-1の約数で、各dについて約数frequency和が欲しい。

素因数指数vectorの各次元で累積し、全divisor下方和をまとめて計算する。

問題固有の要素

到達条件にはA_iとA_jの具体値ではなく二つの位数しか残らないため、同じ位数の入力をfrequencyへ完全に集約できる。

別の問題へ持ち帰る視点: 巡回群の冪関係はelement orderで商を取り、約数poset上の集計問題へ変換できる。

正当性

素数法の乗法群は巡回で各位数の部分群が一意。A_jがA_iの冪であることはord(A_j)|ord(A_i)と同値。位数削減は候補mに対しA^{m/q}=1のときだけqを除くので真の位数へ到達する。指数vectorのprefix zetaは全約数位数の頻度を足し、各始点頻度を掛ければ順序付きの到達組数になる。

実装上の注意

  • Pは10^13なので乗算modには128bit相当を用いる。位数削減では各prime factorを割れる限り反復し、(i,j)は順序付きかつi=jも含む。

復習の核

  • 小さいprimeで全kを周期まで列挙し、A=1、同位数の重複、位数が互いに非整除、P-1がprime power・複数素因数の場合を照合する。

計算量と制約

時間

O(√P+N·Σ_{q|P−1}v_q(P−1)log P+D·s)。D=τ(P−1)、sは相異なる素因数数。

空間

O(N+D)。

制約との対応

公式制約の確認範囲: Time limit: 5 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2 \times 10^5; 1 \leq A_i < P; 2 \leq P \leq 10^{13}; P is prime.; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Discrete Logarithm Problems の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 巡回群を指数化して数える

主題
追加で学ぶ技能
既習技能
  • 法上の四則演算・高速累乗・逆元: 剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。
  • 素因数分解と約数構造: 整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。
  • 約数格子のzeta・Möbius反転: 約数/倍数方向の累積値とexact gcd・period値をnumber-theoretic Möbius関数または格子反転で相互変換する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

主タグ: 巡回群の指数化・位数別数え上げ 乗法的位数・最小周期

補助タグ: 約数格子のzeta・Möbius反転 法上の四則演算・高速累乗・逆元 素因数・約数分解

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

学習の位置

体系上の位置: 巡回群を指数化して数える

  • 巡回部分群を指数と約数格子で分類し、重複を補正して対象を数えられる。
  • 合同式で表された反復の最小周期を乗法的位数に帰着し、約数から求められる。

先に読む単元:

この解説で扱わないこと:

  • 乗法的位数から最小周期だけを求める問題。

学習記録

状況更新: 更新記録なし

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

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

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

同じ単元の問題