garner

関数 · Garner法で連立合同式の解を指定した法で復元する

// (1)
template <class T>
int garner(std::vector<T> r, std::vector<int> m, const int mod);

// (2)
template <int mod>
int garner(std::vector<int> r, std::vector<int> m);

概要

(1) Garner法で連立合同式の解を指定した法で復元する

• テンプレートパラメータ T: 剰余の整数型
• パラメータ r: 各法における剰余
• パラメータ m: 互いに素な法
• パラメータ mod: 出力を取る法
• 戻り値: $x \bmod \mathrm{mod}$
• 計算量: 法の個数を $n$ として $O(n^2)$

(2) Garner法で連立合同式の解を指定した法で復元する

• テンプレートパラメータ mod: 出力を取る法
• パラメータ r: 各法における剰余
• パラメータ m: 互いに素な法
• 戻り値: $x \bmod \mathrm{mod}$
• 計算量: 法の個数を $n$ として $O(n^2)$