동일 방정식과 확장 유클리드 알고리즘
x와 y의 최대공약수가 d일 때
(x,y)=d
방정식으로 변환하면
ax+by=d
매개변수 x와 y에 대한 표현식 x y의 부호는 상관없음
x=x0+kb/d (반대쪽을 더함)
y=y0-ka/d
//확장 유클리드 알고리즘
int extended_gcd(int a, int b, int &x, int &y)//ax=d%(mod b) x와 y는 ax+by=d 방정식의 한 해 반환값은 최대공약수(마지막 레이어의 a)
{
if (!b)
{
x ...
6월 6일 21:47에 게시됨