extended_euclidean

関数 · 中国剰余定理

std::int64_t extended_euclidean(std::int64_t a, std::int64_t b, std::int64_t &x, std::int64_t &y);

概要

拡張ユークリッドの互除法

$ax + by = \gcd(a, b)$ の答えを一つ求める

戻り値

std::int64_t gcd(a, b)

計算量

• $O(\log\min(|a|,|b|))$

関連項目

• chinese_rem — 中国剰余定理