素因数分解と約数構造
概要
素因数・約数分解
整数の条件を素数ごとの指数や約数格子の条件に分解する。
ABC227 Gでは巨大二項係数を実際に作らず、短い分子区間の各素数倍数から指数を取り出す。分母の階乗の指数を引き、残った素因数も集計する。数式に二項係数が現れることよりも、「巨大な値を短い区間上の指数集計へ移す」発想を取り出す。
考え方
整数を素因数指数へ分けると、積は指数の和、約数条件は指数の範囲へ変わる。篩で小さい素数を列挙する方法と、短い巨大区間の倍数から因子を取り出す方法を区別する。
正整数nの試し割りでは残りr=nとし、d=2からd²≤rの間、rがdで割れる限り割って指数e_dを数える。最後にr>1ならr自身が一個の素因数である。既に小さい因子を全て除いたので、合成数が残るなら平方根以下の因子があるはず、という終了条件の根拠になる。n=1は空の素因数集合、0はこの表現へ入れない。
n=∏p^eなら約数は各指数0,…,eの選択を掛け合わせて生成する。lcmは指数のmax、gcdはmin、平方数条件は全指数が偶数、約数個数は∏(e+1)となる。短い巨大区間[L,R]では各素数pについてceil(L/p)pからp刻みで区間配列の残り値を割り、指数を集計する。R以下の全整数を配列化する代わりに区間長と必要な小素数だけを扱うが、残存因子を素数とみなせるには√Rまでの因子を除いた条件などが必要である。
成立条件と計算量
試し割りはO(√U)、通常の篩はO(U log log U)時間・O(U)空間。巨大なUで√U走査が可能とは限らない。約数個数は∏(e_i+1)で、列挙費用は実際の約数数にも比例する。
問題一覧
- ABC400 E「Ringo's Favorite Numbers 3」 公式問題
- ABC393 E「GCD of Subset」 公式問題
- ABC259 E「LCM on Whiteboard」 公式問題
- ABC445 E「Many LCMs」 公式問題組合せ: 法上の四則演算・高速累乗・逆元
技能・出典
主題: 素因数分解と約数構造(整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。)。主タグ: 素因数・約数分解 / 補助タグ: 法上の四則演算・高速累乗・逆元
- ABC420 G「sqrt(n²+n+X)」 公式問題
- ABC412 E「LCM Sequence」 公式問題
- ABC384 F「Double Sum 2」 公式問題
- ABC227 G「Divisors of Binomial Coefficient」 公式問題
技能・出典
主題: 素因数分解と約数構造(整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。)。 C(N,K)自体は作らない。K=min(K,N−K)として分子の短い区間[N−K+1,N]を素数ごとの倍数走査で篩い、分母K!の指数を引く。小素数除去後に残る大素数も集計し、Σではなく∏(e_p+1)で約数数を得る。巨大な整数を短い区間の素因数指数へ写すことが主題。主タグ: 素因数・約数分解
- ABC322 G「Two Kinds of Base」 公式問題組合せ: 交換論から選択順を導く
技能・出典
主題: 素因数分解と約数構造(整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。)。既習技能: 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC212 G「Power Pair」 公式問題主題: 巡回群を指数化して数える
技能・出典
主題: 巡回群を指数化して数える(巡回部分群を指数と約数格子で分類し、重複を補正して対象を数えられる。)。既習技能: 素因数分解と約数構造(整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。) / 約数格子のzeta・Möbius反転(約数/倍数方向の累積値とexact gcd・period値をnumber-theoretic Möbius関数または格子反転で相互変換する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / gcd不変量・差分構造(gcd不変量によって共通因子・差分・周期成分を分離し、rangeまたは剰余類ごとの問いを処理できる。)。主タグ: 巡回群の指数化・位数別数え上げ / 補助タグ: 約数格子のzeta・Möbius反転、gcd不変量・差分構造、素因数・約数分解
- ABC222 G「222」 公式問題主題: 乗法的位数から最小周期を求める
技能・出典
主題: 乗法的位数から最小周期を求める(合同式で表された反復の最小周期を乗法的位数に帰着し、約数から求められる。)。既習技能: 素因数分解と約数構造(整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。) / gcd不変量・差分構造(gcd不変量によって共通因子・差分・周期成分を分離し、rangeまたは剰余類ごとの問いを処理できる。)。主タグ: 乗法的位数・最小周期 / 補助タグ: gcd不変量・差分構造、素因数・約数分解
- ABC230 G「GCD Permutation」 公式問題
技能・出典
主題: 約数格子のzeta・Möbius反転(約数/倍数方向の累積値とexact gcd・period値をnumber-theoretic Möbius関数または格子反転で相互変換する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 素因数分解と約数構造(整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。)。主タグ: 約数格子のzeta・Möbius反転 / 補助タグ: 素因数・約数分解
- ABC238 G「Cubic?」 公式問題主題: 乱択代数fingerprint
技能・出典
主題: 乱択代数fingerprint(multiset・素因数指数vector・巨大整数式をランダムな体元やXOR和へ写し、非同値対象が衝突する確率を評価する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 素因数分解と約数構造(整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。)。主タグ: 乱択代数fingerprint / 補助タグ: 素因数・約数分解
- ABC245 Ex「Product Modulo 2」 公式問題
技能・出典
主題: 一次合同・CRTで解の類を統合する(合同条件の可解性を判定し、逆元・一次合同・CRTで解の類を構成できる。)。既習技能: 固定線形遷移を巨大回数進める(固定線形遷移を行列または漸化式にし、巨大回数後の値を求められる。) / 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 素因数分解と約数構造(整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。)。主タグ: 一次合同・CRT / 補助タグ: 線形遷移・行列累乗、法上の四則演算・高速累乗・逆元、素因数・約数分解
- ABC272 G「Yet Another mod M」 公式問題
技能・出典
主題: 乱択の成功条件と誤り確率を設計する(乱数で選ぶ対象と成功条件を定め、誤り確率を上から評価して必要な反復回数または決定的な事後検証を設計できる。)。既習技能: 素因数分解と約数構造(整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。)。主タグ: 乱択・Monte Carloアルゴリズム / 補助タグ: 素因数・約数分解
- ABC285 Ex「Avoid Square Number」 公式問題
技能・出典
主題: 包除・Möbius反転で重複を補正する(条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。)。既習技能: 素因数分解と約数構造(整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。) / 組合せを生成関数へ符号化する(組合せの合成を生成関数の積・逆数・畳み込みに符号化できる。) / 組合せ係数と対称性で数える(選択・順列・分配の重複の有無を識別し、組合せ係数の式を立てられる。)。主タグ: 集合上の包除原理 / 補助タグ: 組合せ係数・数え上げ、生成関数による組合せ構造の符号化、素因数・約数分解
- ABC304 F「Shift Table」 公式問題
技能・出典
主題: 約数格子のzeta・Möbius反転(約数/倍数方向の累積値とexact gcd・period値をnumber-theoretic Möbius関数または格子反転で相互変換する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 素因数分解と約数構造(整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。)。主タグ: 約数格子のzeta・Möbius反転 / 補助タグ: 法上の四則演算・高速累乗・逆元、素因数・約数分解
- ABC335 G「Discrete Logarithm Problems」 公式問題主題: 巡回群を指数化して数える
技能・出典
主題: 巡回群を指数化して数える(巡回部分群を指数と約数格子で分類し、重複を補正して対象を数えられる。)。追加で学ぶ技能: 乗法的位数から最小周期を求める(合同式で表された反復の最小周期を乗法的位数に帰着し、約数から求められる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 素因数分解と約数構造(整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。) / 約数格子のzeta・Möbius反転(約数/倍数方向の累積値とexact gcd・period値をnumber-theoretic Möbius関数または格子反転で相互変換する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 巡回群の指数化・位数別数え上げ、乗法的位数・最小周期 / 補助タグ: 約数格子のzeta・Möbius反転、法上の四則演算・高速累乗・逆元、素因数・約数分解
- ABC349 F「Subsequence LCM」 公式問題
技能・出典
主題: subset zeta・Möbius変換(Boolean lattice上のsubset/superset和とexact値をzeta変換・Möbius反転で相互変換する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 素因数分解と約数構造(整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。)。主タグ: subset zeta・Möbius変換 / 補助タグ: 法上の四則演算・高速累乗・逆元、素因数・約数分解
- ABC363 F「Palindromic Expression」 公式問題主題: 成立証明から構成解を復元する
技能・出典
主題: 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。既習技能: 素因数分解と約数構造(整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。)。主タグ: 構成解・witness復元 / 補助タグ: 素因数・約数分解
- ABC368 F「Dividing Game」 公式問題主題: ゲーム状態の勝敗とGrundy数
技能・出典
主題: ゲーム状態の勝敗とGrundy数(後続状態から勝敗またはGrundy数を導き、ゲームの初期状態を分類できる。)。既習技能: 素因数分解と約数構造(整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。)。主タグ: game状態・Grundy DP / 補助タグ: 素因数・約数分解
- ABC403 F「Shortest One Formula」 公式問題主題: 最小十分状態からDPを設計する
技能・出典
主題: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。既習技能: 素因数分解と約数構造(整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。) / 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。主タグ: DPの最小十分状態 / 補助タグ: 構成解・witness復元、素因数・約数分解
- ABC428 G「Necklace」 公式問題主題: 群作用・軌道数え上げ
技能・出典
主題: 群作用・軌道数え上げ(群作用の固定点数を群要素のcycle typeごとに数え、BurnsideまたはPólyaの平均でorbit数を求められる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 素因数分解と約数構造(整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。) / 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。主タグ: 群作用・軌道数え上げ / 補助タグ: 資源軸knapsack DP、法上の四則演算・高速累乗・逆元、素因数・約数分解
- ABC461 F「Total Product is N」 公式問題主題: 資源・容量DP
技能・出典
主題: 資源・容量DP(資源軸の上限と更新順を選び、選択の重複を避けられる。)。既習技能: 素因数分解と約数構造(整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。)。主タグ: 資源軸knapsack DP / 補助タグ: 素因数・約数分解
前提・学習成果・出典
習得対象の目安: 緑色(800–1199)。試し割りや篩を使い、素因数の指数と約数に条件を分解する。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 数論。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-prime-divisor
習得する技能
- 整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: 約数格子のzeta・Möbius反転、Gaussian整数・二平方和、Min_25・Lucy DP型の総和篩、乗法的位数から最小周期を求める。
初歩的な素因数分解を、指数vectorと約数格子へ条件を分解する道具として発展させる。
このUnitでは扱わないもの
- 床関数や整数根の値が一定となる区間への分割。