chinese_rem

関数 · 中国剰余定理

template <class T, class U>
std::pair<std::int64_t, std::int64_t> chinese_rem(const std::vector<T> &b, const std::vector<U> &m);

概要

中国剰余定理

任意の i において、x % m_i = b_i となる x を求める

戻り値

std::pair<std::int64_t, std::int64_t> $(r, M)$（$x = r + Mk$、$k$ は整数）

計算量

• 式の個数を $n$、法の積を $M$ として $O(n\log M)$

関連項目

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