ABC 212 G — Power Pair

考察

x=0 なら正の整数 n に対して x^n=0 なので、寄与する組は (x,y)=(0,0) の 1 組だけである。残る非零剰余を乗法群として扱えばよい。

P が素数なので非零剰余は位数 m=P-1 の巡回群をなす。原始根 r を取り x=r^a,y=r^b と書くと、ある n で x^n=y となる条件は an≡b (mod m) へ移る。

採用する候補: 原始根の指数へ写し、g=gcd(m,a) ごとに指数 a の個数と到達可能な b の個数を約数上で集約する。

寄与は g=gcd(m,a) だけで決まり、g は m の約数に限られる。m<10^12 の約数数は高々 6720 なので、約数列挙と約数間の差し引きで制約内に収まる。

棄却する候補: a=1..m を全走査し、各 a について m/gcd(m,a) を答えへ加える。

式自体は正しいが O(P) となり P≤10^12 に間に合わないため、同じ gcd を持つ a をまとめる必要がある。

an≡b (mod m) が n について解を持つのは gcd(m,a) が b を割るときに限る。したがって固定した a から到達できる b は m/gcd(m,a) 個であり、a の gcd ごとに寄与をまとめられる。

m の約数を降順に処理し、f(g)=m/g−Σ_{h:g|h,h>g}f(h) により gcd(m,a)=g となる a の個数を求める。最後に (0,0) の寄与を含む 1+Σ_g f(g)(m/g) を mod 998244353 で計算する。

典型の発動条件

原始根による指数化

発動条件: 素数法の非零剰余に積と冪が現れるとき。

乗法群を Z/(P-1)Z の加法的な指数へ写す。

約数上の包除的集計

発動条件: 値が gcd(P-1,a) のみに依存するとき。

倍数側の個数を大きい約数から差し引き、gcd が各約数に等しい個数を得る。

問題固有の要素

x=0 を非零剰余の巡回群から先に分離すると、残りを原始根の指数だけで統一できる。

別の問題へ持ち帰る視点: 演算が有限体の乗法に閉じる部分と例外値を分け、群構造へ写せる範囲を確認する。

正当性

非零剰余を原始根の指数aに写す。an≡bの可解条件はgcd(a,P−1)|bなので到達先数は(P−1)/g。gcdがgの指数数f(g)は、gの倍数である指数(P−1)/g個からgcdが真の倍数である分を除くことで得られる。よってΣf(g)(P−1)/gは全非零組を一度数え、最後の1が(0,0)を補う。

実装上の注意

  • m の全約数を列挙して大きい順に処理し、f(g) からは g の真の倍数に対応する既計算値だけを差し引く。最後に巡回群外の (0,0) を 1 組加える。
  • m/g と f(g) はそれぞれ 10^12 規模になり得るため、両因子を mod 998244353 へ落としてから 64-bit 整数で掛ける。

復習の核

  • 固定した a に対する冪写像の像の大きさを gcd から再導出し、P=2 を含む小さい素数で (0,0) の 1 組と約数上の差し引きを全列挙結果に照合する。

計算量と制約

時間

O(√P+D²)、D=τ(P−1)。約数間の倍数関係を全対比較する。

空間

O(D)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq P \leq 10^{12}; P is a prime number.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

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

主題
追加で学ぶ技能
    なし
    既習技能
    • 素因数分解と約数構造: 整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。
    • 約数格子のzeta・Möbius反転: 約数/倍数方向の累積値とexact gcd・period値をnumber-theoretic Möbius関数または格子反転で相互変換する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
    • gcd不変量・差分構造: gcd不変量によって共通因子・差分・周期成分を分離し、rangeまたは剰余類ごとの問いを処理できる。

    主タグ: 巡回群の指数化・位数別数え上げ

    補助タグ: 約数格子のzeta・Möbius反転 gcd不変量・差分構造 素因数・約数分解

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

    学習の位置

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

    • 巡回部分群を指数と約数格子で分類し、重複を補正して対象を数えられる。

    先に読む単元:

    • 約数格子のzeta・Möbius反転 — 素因数・約数分解で得た考え方と実装を再利用し、約数格子のzeta・Möbius反転の発動条件・正当化・境界を重複なく学ぶ。
    • gcd不変量・差分構造 — 差・周期・range条件に共通するgcd不変量を抽出し、共通因子や剰余classを分離する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
    • 乗法的位数から最小周期を求める — 合同算術と約数分解を使えることを前提に、最小周期を乗法的位数へ帰着して約数から絞る。
    • 素因数分解と約数構造 — 初歩的な素因数分解を、指数vectorと約数格子へ条件を分解する道具として発展させる。

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

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

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題