Bézout等式・一次不定方程式
整数線形結合がgcdの倍数全体になることを使い、一次不定方程式の可解性と解のparameter表示を得る。
この典型を扱う単元: gcdと整数解の成立条件
検索別名: Bézout等式、extended Euclidean algorithm、一次不定方程式、拡張Euclid
未知問からこの典型を見つける手掛かり
- 扱う対象
- gcd
- 整数係数
- 線形結合
- 使う手掛かり
- ax\+by=c
- 整数解
- 保つ不変量
- gcd divides c
- 一般解
- 求めるもの
- 可解判定
- 整数解構成
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 数論構造への変換
関連する典型
学習成果と学習単位
整除条件や一次不定方程式の可解性をgcdで特徴付け、必要なら拡張EuclidでBézout整数解を構成できる。
gcdと整数解の成立条件で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC271 Ex「General General」 公式問題主題: gcdと整数解の成立条件 / 主タグ
- ABC459 G「Golf 2」 公式問題主題: 二変数の凸区分線形整数最適化 / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC271 Ex「General General」 公式問題主題: gcdと整数解の成立条件 / 主タグ
- ABC315 G「Ai + Bj + Ck = X (1 <= i, j, k <= N)」 公式問題主題: gcdと整数解の成立条件 / 主タグ
- ABC340 F「S = 1」 公式問題主題: gcdと整数解の成立条件 / 主タグ
- ABC459 G「Golf 2」 公式問題主題: 二変数の凸区分線形整数最適化 / 主タグ