BOJ 14565 - 역원 구하기 (확장 유클리드)

https://www.acmicpc.net/problem/14565

 

<문제설명>

임의의 정수 a,n (a<n<=1e12)에 대해서 a의 모듈러 n에 대한 음이아닌 정수 덧셈역원과 곱셈역원 출력

 

<풀이>

덧셈역원: a<n 이므로 n-a

 

곱셈역원을 x라고 둔다면 a,x,n은 다음 식을 만족한다.

x를 구하기 위해선 거꾸로 접근해야 한다.

 

'a와 n이 서로소이다' 와 'ax+ny =1 의 해가 존재한다'는 필요충분 조건이다. (0<a,n)

 

ax+ny=1의 양 변을 모듈로 n 해주면

ax % n = 1  즉, 다음과 같다.

 

따라서 a와 n이 서로소가 아니라면 곱셈의 역원이 없는 것이고,

a와 n이 서로소라면 ax+ny=1의 근 중 아무 x값이나 선택하여 곱셈의 역원으로 삼으면 된다.

 

 

<코드>

ll n, a;
T euclid(ll x, ll y) {
	if (x < y) swap(x, y);
	if (y == 0) return { x,1,0 };

	ll g, x1, y1; tie(g, x1, y1) = euclid(y, x%y);
	return { g, y1, x1 - (x / y) * y1 };
}

int main() {
	FAST; cin >> n >> a;
	cout << n - a << " ";
	ll g, x, y;
	tie(g, x, y) = euclid(n, a);
	if (g != 1) {
		cout << -1 <<'\n';
	}
	else {
		cout << (y+n)%n << '\n';
	}
}

코드에선 nx+ay = 1의 근을 찾아준거라 y값의 모듈로 n를 출력했다.