[C++] 백준 14565번 : 역원(Inverse)구하기

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

14565번: 역원(Inverse) 구하기

이 문제는 정수론을 공부를 하고 확인 문제용으로 좋을 듯한 문제다.

역원을 구하기에 앞서,

'모듈러연산', '합동식', '항등원'..등에 대해 알아보아야 한다.

---

1. 합동식

a,b를 정수 m으로 나눈 나머지가 같을 때, a와 b는 법 m에 대해 합동이라한다.
a = b mod m

예를 들어 1시와 13시가 같은 오후 1시를 나타낸다고 할 수 있고,
식으로 표현하면, 13 = 1 mod 12 라고 할 수 있다.

2. 항등원과 역원

(*는 +또는 x)

항등원 

: 임의의 원소 a와 연산 *에 대해서 a*e = e*a = a를 만적하는 원소 e
따라서, +연산에서 항등원은 0, x에 대해서 항등원은 1

역원 

: a*a^-1 = a^-1*a = e를 만족하는 a^-1
따라서 2의 대한 +연산의 역원은 -2, x연산의 역원은 1/2

여기서 만약 곱셈에 대한 역원이 존재하지 않는다면, 나눗셈은 정의할 수 없음

3. 모듈로 연산 사칙 연산

모듈로 연산자 : mod (%)
나머지 연산자라 생각하면 된다.
예를 들어. 4 mod 3 = 1은

4를 3으로 나눈 나머지와 1을 3으로 나눈 나머지가 같다. 라는 말과 같다.

이런 모듈로 연산은

덧셈 : (a+b) % M = ((a % M)+(b % M)) % M
뺄셈 : (a−b) % M = ((a % M)−(b % M)+M) % M
곱셈 : (a×b) % M =((a % M)×(b % M)) % M

 

이 존재하고
특히 곱셈역원은

1. 유클리드호제법 

2. 페르마 소정리

3. 동적계획(DP) 로 구할 수 있다.

나눗셈은 곱셈역을 통해 가져오는 것이며

a % b = p

에서 a와 p는 서로 서로소인 관계여야한다. (페르마 소정리에서 증명할 수 있다.)

 

4. 페르마 소정리

 

유클리드 호제법은 나중에 알아보도록하고,

페르마 소정리부터보자..

내가 정말 이 공식이 어떻게 나오게 되었는지 이해하고 싶어서, 유튭강의도 정말 많이 찾아보고, 글도 많이 읽어봤는데,,

나의 이 댕청한 뇌로는 납득이 가지 않았다..

마음이 아프지만, 그냥 외우기로 했다. 하하..

 

알고의 신한테 물어봤더니 코테에서 중요한 내용은 아니라고 해서 (사실 dp가 제일 어려운 수준이라 했다.) 그냥 일단 이쯤에서 받아드리자..

 

무튼 개념은 대충 정리했으니까 다시 문제로 돌아와서 풀어보자

이 역원구하기 문제는 결국 곱셈의 역원을 구하는 것이 핵심이다.

앞서 전달한 것처럼 곱셈의 역원을 구할 때는 세가지 방법을 활용할 수 있고,

나는 유클리드를 통해 문제를 풀어보았다.

놀랍게도 열심히 페르마 소정리를 공부했지만, 유클리드로 풀었다.

왜냐면 이거 가르쳐준 선생님의 풀이중에 내가 납득한게 유클리드 뿐이었다..ㅎ

(나중에 동적계획법이 페르마소정리로도 풀어보면 좋겠어)

 

(logic)

- 𝑎𝑋 ≡ 1 𝑚𝑜𝑑 𝑛 or;𝑎 %𝑛 = 1

- EEu(a,;n);->;gcd (a,;n),;x,;y
- 1. gcd(a,;n)이 1이 아닌 경우 -> 역원이 존재할 수 없으므로 ”-1” 출력
- 2.;gcd(a,;n)이 1인 경우 -> 만족하는 x의 값을 양수로 만든 X의 값 출력 (kn을 더하여도 성립)

 

#include <iostream>
#include <stack>
#include <vector>
#include <cmath>
#include <utility>

#include<algorithm>

using namespace std;
typedef long long ll;
ll n, a;

//14565



//gcd
long long gcd (long long q, long long r) {
	if (r == 0) return q;
	return gcd (r, q%r);
}

//extensvie
pair<ll, pair<ll, ll>> EEu (ll a, ll b) {
	ll r0 = a, r1 = b;
	ll x0 = 1, x1 = 0;
	ll y0 = 0, y1 = 1;
	ll q;
	
	while (r1) {
//			cout << x0 << " " <<  x1 << " " << y0 << " " << y1 << " " << r0 << " " << r1 <<endl;
		q = r0 / r1;
		
		// r0, r1
		r0 = r0 % r1;
		swap (r0,r1);
		
		// x0, x1
		x0 = x0 - x1 * q;
		swap (x0, x1);
		x1 %= b;
		
		// y0, y1
		y0 = y0 - y1 * q;
		swap (y0, y1);
		y1 %= a;
		
//		cout << x0 << " " <<  x1 << " " << y0 << " " << y1 << " " << r0 << " " << r1 <<endl;
	}
	
	
	return { r0, {x0, y0}};
}

ll plusInverse(ll n, ll a) {
	
	ll b = n - a;
	
	return b;
	
}

ll multipleInverse(ll n, ll a) {
	
	if (gcd(a, n) == 1) { //exist
		
		pair<ll, pair<ll, ll>> rst = EEu(a,n);
		
		if (rst.second.first < 0) {
			return n + rst.second.first;
		} else {
			return  rst.second.first;
		}
		
//		cout << rst;
		return rst.second.second;

	} else {
			pair<ll, pair<ll, ll>> rst = EEu(n,a);
		return -1;
	}
}


int main() {

	cin >> n >> a;
	
	ll plus = plusInverse(n,a);
	
	ll multiple = multipleInverse(n,a);
	
	
	cout << plus << " " << multiple << endl;

	return 0;
}