素因数分解と約数構造

概要

素因数・約数分解

整数の条件を素数ごとの指数や約数格子の条件に分解する。

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)で、列挙費用は実際の約数数にも比例する。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 緑色(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では扱わないもの

  • 床関数や整数根の値が一定となる区間への分割。

根拠