확장 유클리드 호제법

$ax+by=c$ 의 해를 찾는 방법

먼저 $c$가 $gcd(a,b)$의 배수가 되어야 한다. 만약 $gcd(a,b)$의 배수가 아니라면 좌변은 $gcd(a,b)$로 나누어 떨어지지만 우변은 안 나눠떨어지기 때문에 모순이다.

따라서 우리는

$$ax+by=gcd(a,b)$$

의 해를 구할 것이다. 그리고 한가지 짚고 넘어가야 하는 점은 $ax+by$의 꼴은 항상 $gcd(a,b)$의 배수이다.

$a=bq+r (단, b>r\geq0)$ 라 하자

주어진 식에 $a$값을 대체 하면

$(bq+r)x+by=gcd(bq+r,b)$ 이 되고 정리하면

$$ b(qx+y)+rx = gcd(r,b) $$ 이 된다.

 

가운데 정렬한 두 식을 비교하자.

만약 아래식 $bx'+ry'=gcd(b,r)$의 해를 $(x',y')$를 구했다면 원래 구하고자 하는 식의 해는 $(y',x'-y'q)$가 될 것이다.

그리고 이 과정은 유클리드 호제법에 의해 $r=0$일 때까지 진행될 것이다. $r=0$ 일 때의 해는 $bx+0\cdot y=b$ 의 꼴일것이다. 따라서 마지막의 해는 $(1,0)$ 이 된다.

이 전체 과정을 코드로 표현해 보자.

typedef pair<int,int> P;
//ax+by=gcd(a,b) 의 해(x,y) 를 반환한다.
P solve(int a,int b){
    if(b==0) return P(1,0);
    P next=solve(b,a%b);
    return P(next.second,next.first-next.second*(a/b));
}
 

 

이런 식으로 알고리즘을 구할 수 있기 때문에 $ax+by=gcd(a,b)$ 의 해는 분명히 존재한다.

 

 

마찬가지로 $a_1x_1+a_2x_2+\cdot\cdot\cdot+a_nx_n=gcd(a_1,a_2,...,a_n) $의 해도 분명히 존재함을 밝힐 수 있다.

$a_1x_1+a_2x_2=k\cdot gcd(a_1,a_2)(\forall k\in Z)$의 해가 존재하기 때문에

위 식은 

$gcd(a_1,a_2)k+\cdot\cdot\cdot +a_nx_n=gcd((gcd(a_1,a_2),..,a_n))$

의 해를 구하는 것으로 바뀐다. 즉, 귀납적으로 해가 존재함이 증명되었다.

이를 이용하면 

 

BOJ 2926 자와 각도기

을 쉽게 풀 수 있다.

주어진 작도가능한 각도와 추가로 360도 까지의 최대공약수를 구해놓으면 그 최대 공약수($g$라 하자.)의 배수에 해당하는 모든 각도를 만들수 있음 뿐더러 오직 그 각도만 만들 수 있음이 증명된다.

따라서 앞으로 주어지는 $k$개의 각도가 $g$로 나누어떨어지는지 안나눠떨어지는지만 확인하면 된다.

 

확장 유클리드 호제법은 codefores를 풀던 중 

Santa's Bot

를 풀다가 공부하게 되었다.

바로 분수 꼴의 modular를 계산해야하는 문제이다.

위의 알고리즘으로 부터 modular(MOD)의 a의 대한 역원을 구할 수 있다

그것은 $ax+MOD\cdot y=gcd(a,MOD)=1$ 를 통해 $x$값을 구하면 된다.

 

코드: 68235922

 

 

 

참고 사이트: https://casterian.net/archives/601