多項式 GCD（軽量版）

fps/polynomial_gcd_light.hpp · GitHub で見る

共通ページ · 軽量実装

多項式 GCDの高速実装はこちら

#include "lib/fps/polynomial_gcd_light.hpp"

light_fps a{mint(-1), 0, 1};
light_fps b{mint(-1), 1};
auto g = light_fps_algorithms::polynomial_gcd(a, b);
auto [d, x, y] = light_fps_algorithms::polynomial_extended_gcd(a, b);
auto inverse = light_fps_algorithms::polynomial_inv_mod(light_fps{1, 1}, light_fps{1, 0, 1});

軽量 FPS の LightFormalPowerSeries<T> を使う多項式 GCD です。係数は定数項から並べ、法は 998244353 とします。既定の light_fps・mint に加え、軽量 FPS の要件を満たす同じ法の modint 型も使えます。

関数・型	内容・返り値
light_fps_algorithms::polynomial_gcd(a,b)	最高次係数を 1 にした最大公約多項式
light_fps_algorithms::polynomial_extended_gcd(a,b)	a*x+b*y=gcd を満たす PolynomialExtendedGCD<T>{gcd,x,y}
light_fps_algorithms::PolynomialExtendedGCD<T>	gcd・x・y は LightFormalPowerSeries<T>。構造化束縛が可能
light_fps_algorithms::polynomial_inv_mod(a,modulus)	a*h ≡ 1 mod modulus を満たす optional<LightFormalPowerSeries<T>>。逆元がなければ nullopt

入力は変更しません。入力・出力とも不要な末尾の 0 を除き、零多項式は空配列とします。gcd(0,0) は零多項式、拡張 GCD は三つの空配列を返します。片方だけが 0 なら、もう片方を最高次係数 1 に正規化します。

polynomial_inv_mod の法多項式は非零にします。法が非零の定数なら、空配列を持つ optional を返します。それ以外では GCD が 1 のときに限り逆元が存在し、返り値の次数は法多項式の次数未満です。FPS の f.inv() が求める \(x^n\) を法とする逆数とは別の操作です。

通常版はこちら。

入力の最大係数数は \(2^{22}\) 以下とします。最大係数数を \(n\)、畳み込みの計算量を \(M(n)\) として、各関数は \(O(M(n)\log n)=O(n\log^2 n)\) 時間、追加空間は \(O(n)\) です。

依存ライブラリ

• 軽量 FPS の共通実装
• 軽量 FPS の基本演算
• 軽量 FPS の NTT
• 軽量 FPS の疎演算
• 疎 FPS の項収集・演算種別
• 多項式 Half-GCD（軽量版）
• 多項式の積・打ち切り積の共通処理
• 多項式の共通積木
• 軽量な形式的冪級数
• modint998244353

検証コード

• test/fps_light_polynomial_extended_gcd.test.cpp
• test/fps_light_polynomial_gcd.test.cpp
• test/fps_light_polynomial_inv_mod.test.cpp

コード

#ifndef CP_FPS_POLYNOMIAL_GCD_LIGHT_HPP
#define CP_FPS_POLYNOMIAL_GCD_LIGHT_HPP

#include "../components/polynomial_half_gcd_light.hpp"
#include <optional>

namespace light_fps_algorithms {
template<class T>
struct PolynomialExtendedGCD {
	LightFormalPowerSeries<T> gcd, x, y;
};

template<class T>
LightFormalPowerSeries<T> polynomial_gcd(LightFormalPowerSeries<T> a, LightFormalPowerSeries<T> b) {
	a.shrink(), b.shrink();
	fps_light_detail::PolynomialHalfGCD<T>::reduce(a, b);
	if (!a.empty()) a /= a.back();
	return a;
}

template<class T>
PolynomialExtendedGCD<T> polynomial_extended_gcd(LightFormalPowerSeries<T> a, LightFormalPowerSeries<T> b) {
	a.shrink(), b.shrink();
	if (a.empty() && b.empty()) return {};
	using H = fps_light_detail::PolynomialHalfGCD<T>;
	typename H::Matrix matrix;
	H::reduce(a, b, &matrix);
	T inverse = a.back().inv();
	a *= inverse, matrix.a[0] *= inverse, matrix.a[1] *= inverse;
	return {std::move(a), std::move(matrix.a[0]), std::move(matrix.a[1])};
}

template<class T>
std::optional<LightFormalPowerSeries<T>> polynomial_inv_mod(LightFormalPowerSeries<T> a, LightFormalPowerSeries<T> modulus) {
	modulus.shrink();
	assert(!modulus.empty());
	if (modulus.size() == 1) return LightFormalPowerSeries<T>{};
	a = a.divmod(modulus).second;
	auto result = polynomial_extended_gcd(std::move(a), modulus);
	if (result.gcd.size() != 1) return std::nullopt;
	return result.x.divmod(modulus).second;
}
}

#endif

Back to top page