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

안녕하세요. 오늘은 역원을 구할 거예요.

문제

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

아이디어

덧셈역은... 구할수 ... 있죠...?
B=N-A입니다.

곱셈역이 약간 어려운데 AC가 N으로 나눈 나머지가 1이므로 AC=Nk+1 (k는 정수)의 꼴로 나타낼 수 있고 AC-Nk=1이 됩니다. 이때 정수근 (C,k)가 존재할 필요충분조건은 gcd(A,N)=1이라는 것이므로 이를 만족하지 않는다면 -1을 출력해주면 됩니다. 만약 이를 만족한다면 유클리드 호제법을 응용해서 정수해를 찾아주면 됩니다.

소스코드

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

ll gcd(ll a, ll b) { return ((b) ? gcd(b, a % b) : a); }
pair <ll, ll> find(ll a, ll b) //ax+by=1 정수해 (x,y)
{
	if (b == 0) return { 1,0 };

	pair <ll, ll> Ans;

	bool swapped = false;
	if (a > b)
	{
		swap(a, b);
		swapped = true;
	}
	pair <ll, ll> temp = find(a, b % a);
	Ans = { temp.first - (b / a) * temp.second ,temp.second };
	
	if (swapped) swap(Ans.first, Ans.second);
	return Ans;
}

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	ll N, A, B, C;

	cin >> N >> A;
	B = N - A;
	if (gcd(N, A) != 1) C = -1;
	else
	{
		C = find(A, N).first;
		if (C < 0) C += N;
	}

	cout << B << ' ' << C;
}

감사합니다.