extended euclidean

확장 유클리드

아래 함수에서 return하는 객체의 요소들의 의미는 다음과 같다.

x	y
x가 될 수 있는 값	y가 될 수 있는 값

extended_solution 구조체의 순서에 유의한다 (x, y) 순

struct extended_solution {
	long long x, y;
};

extended_solution extended_gcd(long long a, long long b) {
	long long old_s = 1, old_t = 0, old_r = a;
	long long new_s = 0, new_t = 1, new_r = b;

	while (new_r != 1) {
		long long q = old_r / new_r;
		long long temp;

		// update new, old value;
		temp = old_r;
		old_r = new_r; 
		new_r = temp % new_r;

		temp = old_s;
		old_s = new_s; 
		new_s = temp - new_s*q;

		temp = old_t;
		old_t = new_t; 
		new_t = temp - new_t*q;
	}

	return extended_solution{ new_s,new_t };
}