[BOJ 14565 // C++] 역원(Inverse) 구하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 14565번 문제인 역원(Inverse) 구하기이다.
문제는 아래 링크를 확인하자.

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

14565번: 역원(Inverse) 구하기

덧셈의 역원은 단순히 N에서 A를 빼는 것으로 간단히 구할 수 있다.

또한, 곱셈의 역원은 extended euclidean algorithm(확장 유클리드 알고리즘)을 통해 간단히 구할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <tuple>
using namespace std;
typedef long long ll;

tuple<ll,ll,ll> extgcd(ll a, ll b, ll p, ll q, ll r, ll s) {
	if (b == 0) return make_tuple(a, p, r);
	ll tmp = a / b;
	return extgcd(b, a - tmp * b, q, p - tmp * q, s, r - tmp * s);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	ll N, A; cin >> N >> A;
	cout << N - A << ' ';
	ll a, p, r;
	tie(a, p, r) = extgcd(A, N, 1, 0, 0, 1);
	p %= N;
	if (p < 0) p += N;
	if (a == 1) cout << p;
	else cout << -1;
}