프로그램 명: extended_euclid
제한시간: 1 초
양의 정수 A , B 에 대해서 아래 식을 만족하는 정수 X,Y 가 존재하는 것이 확장 유클리드 알고리즘이다.
AX + BY = D , D는 A,B 의 최대 공약수
문제는 A,B 가 주어질 때 X,Y 와 D 를 찾는 것이다.
입력
입력은 정수 A, B 가 주어진다.(A,B<1 000 000 001)
출력
입력에 대해서 X,Y,D 를 출력한다.
만약 여러개의 X,Y 가 존재한다면 첫 째 기준은 |X| + |Y| 가 최소인 쌍을 그리고 X <= Y 인 순으로 출력한다.
입출력 예
입력
4 6
출력
-1 1 2
입력
17 17
출력
0 1 17
참고
확장유클리드문제에서
입력받을 두 수를 gp,gq라고 잡으면,(단, pㅗq (ㅗ는 기하학에서는 수직, 정수론에서는 서로소를 나타냅니다.)) 현재 gpx+gqy=g가 되는 x, y를 찾는거니까
px+qy=1이 된다면 충분합니다.
여기서 이 부정방정식의 일반해를 구할 수 있습니다.
- 임의의 해를 구합니다.(a1, a2)
- 그러면 (x,y)=(a1+yk, a2-xk)꼴의 일반해를 갖습니다.(여기서 k는 정수입니다. 그리고 직접 대입하면 참임을 알 수 있습니다.)
출처:acm
소스+참고 글:Aelixir
[질/답]
[제출 현황]
[푼 후(12)]