BezoutIdentity 構造体

一次不定方程式 ax+by=c を解く verify: https://atcoder.jp/contests/abc340/submissions/62495050 [詳解]

#include "bezout_identity.hpp"

公開メンバ関数
	BezoutIdentity (ll a, ll b, ll c)
	ax+by=c
bool	build ()
	解が存在するか否かを返す
pair< ll, ll >	general_solution (ll t=0)
	一般解を返す

詳解

一次不定方程式 ax+by=c を解く verify: https://atcoder.jp/contests/abc340/submissions/62495050

g=gcd(a,b) とする。extGCD(a,b) によって、ax'+by'=g を解く。 両辺を c/g 倍し x=x'(c/g),y=y'(c/g) とすると、ax+by=c を満たす。c が g で割り切れない場合、解は存在しない。 ax+by=c の両辺を g で割ると、(a/g)*x + (b/g)*y = c/g となる。方程式の一般解を X,Y とおくと、(a/g)*(X-x) + (b/g)*(Y-y) = 0 を満たす。 a/g と b/g は互いに素なので X-x は b/g の倍数であり、X=(b/g)*t+x となる。 これを再代入すると、Y=-(a/g)*t+y を得る。

bezout_identity.hpp の 13 行目に定義があります。

構築子と解体子

BezoutIdentity()

BezoutIdentity::BezoutIdentity ( ll a, ll b, ll c )

inline

ax+by=c

bezout_identity.hpp の 15 行目に定義があります。

関数詳解

build()

bool BezoutIdentity::build ( )

inline

解が存在するか否かを返す

bezout_identity.hpp の 22 行目に定義があります。

general_solution()

pair< ll, ll > BezoutIdentity::general_solution ( ll t = 0 )

inline

一般解を返す

bezout_identity.hpp の 33 行目に定義があります。

---

この構造体詳解は次のファイルから抽出されました:

• math/bezout_identity.hpp