素因数・約数分解
整数の条件を素数ごとの指数や約数格子の条件に分解する。
この典型を扱う単元: 素因数分解と約数構造
検索別名: prime factorization、sieve、約数列挙、素因数分解
未知問からこの典型を見つける手掛かり
- 扱う対象
- 倍数
- 約数
- 素因数
- 素数
- 使う手掛かり
- 割り切る
- 因数分解
- 約数を列挙
- 保つ不変量
- 一意分解
- 指数
- 素因数ごと
- 求めるもの
- 個数
- 和
- 成立判定
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC445 E「Many LCMs」 公式問題主題: 素因数分解と約数構造 / 主タグ
- ABC259 E「LCM on Whiteboard」 公式問題主題: 素因数分解と約数構造 / 主タグ
- ABC227 G「Divisors of Binomial Coefficient」 公式問題主題: 素因数分解と約数構造 / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC212 G「Power Pair」 公式問題主題: 巡回群を指数化して数える / 補助タグ
- ABC222 G「222」 公式問題主題: 乗法的位数から最小周期を求める / 補助タグ
- ABC227 G「Divisors of Binomial Coefficient」 公式問題主題: 素因数分解と約数構造 / 主タグ
- ABC230 G「GCD Permutation」 公式問題主題: 約数格子のzeta・Möbius反転 / 補助タグ
- ABC238 G「Cubic?」 公式問題主題: 乱択代数fingerprint / 補助タグ
- ABC245 Ex「Product Modulo 2」 公式問題主題: 一次合同・CRTで解の類を統合する / 補助タグ
- ABC259 E「LCM on Whiteboard」 公式問題主題: 素因数分解と約数構造 / 主タグ
- ABC272 G「Yet Another mod M」 公式問題主題: 乱択の成功条件と誤り確率を設計する / 補助タグ
- ABC285 Ex「Avoid Square Number」 公式問題主題: 包除・Möbius反転で重複を補正する / 補助タグ
- ABC304 F「Shift Table」 公式問題主題: 約数格子のzeta・Möbius反転 / 補助タグ
- ABC322 G「Two Kinds of Base」 公式問題主題: 素因数分解と約数構造 / 主タグ
- ABC335 G「Discrete Logarithm Problems」 公式問題主題: 巡回群を指数化して数える / 補助タグ
技能・出典
主題: 巡回群を指数化して数える
主タグ: 巡回群の指数化・位数別数え上げ、乗法的位数・最小周期 / 補助タグ: 約数格子のzeta・Möbius反転、法上の四則演算・高速累乗・逆元、素因数・約数分解
- ABC349 F「Subsequence LCM」 公式問題主題: subset zeta・Möbius変換 / 補助タグ
- ABC363 F「Palindromic Expression」 公式問題主題: 成立証明から構成解を復元する / 補助タグ
- ABC368 F「Dividing Game」 公式問題主題: ゲーム状態の勝敗とGrundy数 / 補助タグ
- ABC384 F「Double Sum 2」 公式問題主題: 素因数分解と約数構造 / 主タグ
- ABC393 E「GCD of Subset」 公式問題主題: 素因数分解と約数構造 / 主タグ
- ABC400 E「Ringo's Favorite Numbers 3」 公式問題主題: 素因数分解と約数構造 / 主タグ
- ABC403 F「Shortest One Formula」 公式問題主題: 最小十分状態からDPを設計する / 補助タグ
- ABC412 E「LCM Sequence」 公式問題主題: 素因数分解と約数構造 / 主タグ
- ABC420 G「sqrt(n²+n+X)」 公式問題主題: 素因数分解と約数構造 / 主タグ
- ABC428 G「Necklace」 公式問題主題: 群作用・軌道数え上げ / 補助タグ
- ABC445 E「Many LCMs」 公式問題主題: 素因数分解と約数構造 / 主タグ
- ABC461 F「Total Product is N」 公式問題主題: 資源・容量DP / 補助タグ