1. 유클리드 호제법 (gcd)

: 두 자연수의 최대 공약수 구하기

gcd(a,b) = gcd(b,a%b)  //a>=b
				 = gcd(b, r) //a%b = r

//방법1.
int gcd1(int a, int b){
	while(b!=0){ //r==0일 때 -> a값이 최대 공약수이다.
		b = a % b; //b=r
		a = b;
	}
	return a;
}

//방법2.
int gcd2(int a, int b){
    int r = a % b;
    while(r!=0){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

2. 확장 유클리드 호제법

2-1) 디오판토스 방정식 (ax+by = c)

: 해가 정수인 부정 방정식(해가 무수히 많음)

ex) 3x+2y = 5 → (1,1) (3,-2) (5,-5) ...

⇒ 일반해를 구할 수 있을까?

2-2) 베주 항등식 (ax+by = gcd(a,b))

: 확장 유클리드 호제법을 사용하여 → ax+by = gcd(a,b)의 해가 되는 특정 정수 s0, t0 쌍을 찾아낼 수 있다.

2-3) 확장 유클리드 호제법

: 디오판토스 부정방정식 ax+by=c에서 → 재귀적인 유클리드 호제법을 사용하여 아래와 같은 일을 할 수 있다.

• 기능

⇒ 1) 해를 구할 수 있는가
			-> c % gcd(a,b) == 0 이어야 해를 구할 수 있다. (c ≥ gcd(a,b))
				 (c가 gcd의 배수여야 한다. == gcd는 c의 약수이다.)

⇒ 2) c == gcd(a,b)일 때의 s0,t0구하기
			-> ax + by = gcd(a,b)일 때의 특정 해 (s0,t0)를 구할 수 있다.

• 예시

ex) 9x + 5y = 1

0. 초기해 구하기 (s,t,r) = (1,0,a) (0,1,b)
1. r == 0 이 될 때까지 유클리드 호제법을 반복한다.
		tmp = s0 - s1 * q
		s0 = s1	
		s1 = tmp
2. r==0이 됐을 때 (s0,t0,r0) 값을 리턴한다.
		s0,t0 -> 특정 해(s0,t0)
		r0 -> a,b의 최대공약수 

2-3-1) 확장 유클리드 호제법 구현

//확장 유클리드 호제법 
//-> ax + by = gcd(a,b)일 때의 특정해 s0,t0,r0(gcd)를 구하자

EGResult extendedGcd(long a, long b){ 
	//초기해 설정
	int s0 = 1, t0 = 0, r0 = a;
	int s1 = 0, t1 = 1, r1 = b;

	long tmp; //swap을 위한 변수
	while(r1!=0){ //r1이 0이 되면 종료
		int q = r0 / r1; //몫
		//r변경
		tmp = r0 - r1 * q;
		r0 = r1;
		r1 = tmp;

		//s변경
		tmp = s0 - s1 * q;
		s0 = s1;
		s1 = tmp;

		//t변경
		tmp = t0 - t1 * q;
		t0 = t1;
		t1 = tmp;
	}
	return new EGResult(s0,t0,r0); //r1==0일 때의 값 리턴
}

class EGResult{
	long s;
	long t;
	long r;

	//생성자 ...
}