[백준 14565] 역원(Inverse) 구하기

문제 링크 => https://www.acmicpc.net/problem/14565

14565번: 역원(Inverse) 구하기

---

N과 A이 주어질 때, 덧셈에 대한 역원과 곱셈에 대한 역원을 구하는 문제이다.

 

덧셈의 역원 => A + x = 0 (mod N) 이므로 x = N - A 이다. 이때, 1 <= A < N 라고 주어졌기 때문에 N-A 자체가 답이다.

x = N - A 이면 A + (N - A) = N = 0 (mod N) 이므로 성립한다.

 

곱셈의 역원 => Ax = 1 (mod N) 인데 x를 구하는건 쉽지 않다.

 

따라서 Extended Euclidean Algorithm 을 이용해서 A의 inverse를 구해야 한다.

 

아이디어는 Ax = 1 (mod N) => Ax + Ny = 1 에서 gcd(A, N), x, y 를 구하는 것이다.

 

이때, gcd(A, N) 값이 1인 경우 x가 inverse이다. (x<0 일때 x+N)

 

그러나 gcd(A, N) 값이 1이 아닌 경우 A에 대한 inverse x는 존재하지 않는다.

 

풀이 code

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

pair<ll, pair<ll, ll>> xGCD(ll a, ll b) { // returns {g, {x, y}}, ax+by=g
	if(b==0) return { a,{1,0} }; // base case
	pair<ll, pair<ll, ll>> ret=xGCD(b, a%b);
	ll g, x, y;
	g=ret.first;
	tie(x, y)=ret.second;
	return { g,{y,x-(a/b)*y} }; 
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	ll N, A;
	cin>>N>>A;
	pair<ll, pair<ll, ll>> res=xGCD(A, N);
	ll g, x, y;
	g=res.first;
	tie(x, y)=res.second;

	if(g==1) {
		cout<<N-A<<" "<<(x<0 ? x+N:x);
	}
	else {
		cout<<N-A<<" "<<-1;
	}

	return 0;
}