剰余周期・指数法則
有限剰余状態の周期またはFermat/Euler型指数簡約を示し、巨大な反復やtower exponentを短縮する。
この典型を扱う単元: 剰余周期と指数法則を利用する
検索別名: Eulerの定理、Fermatの小定理、modular periodicity、剰余周期
未知問からこの典型を見つける手掛かり
- 扱う対象
- 剰余列
- 巨大指数
- 有限状態
- 使う手掛かり
- 反復回数が巨大
- 指数を法で簡約
- 保つ不変量
- 前周期
- 可逆性
- 周期
- 求めるもの
- 巨大反復の値
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 数論構造への変換
関連する典型
学習成果と学習単位
剰余類上の周期または指数法則を示し、周期状態の前計算や巨大指数の簡約で値を求められる。
剰余周期と指数法則を利用するで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC228 E「Integer Sequence Fair」 公式問題主題: 剰余周期と指数法則を利用する / 主タグ
- ABC319 E「Bus Stops」 公式問題主題: 剰余周期と指数法則を利用する / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC228 E「Integer Sequence Fair」 公式問題主題: 剰余周期と指数法則を利用する / 主タグ
- ABC286 F「Guess The Number 2」 公式問題主題: 一次合同・CRTで解の類を統合する / 主タグ
- ABC319 E「Bus Stops」 公式問題主題: 剰余周期と指数法則を利用する / 主タグ
- ABC320 G「Slot Strategy 2 (Hard)」 公式問題主題: 二部matching・Hall・Kőnig / 補助タグ
技能・出典
主タグ: 二部matching・Hall・Kőnig / 補助タグ: 座標・値の順序保存圧縮、貪欲法と交換論、剰余周期・指数法則、単調境界探索