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

문제

14565번: 역원(Inverse) 구하기

덧셈 역원(b)과 곱의 역원(c)으로 구하는 문제 입니다.

예를 들어 n = 26, a = 11이면 

11 + b mod 26 = 0 을 만족하는 b와

11c mod 26 = 1을 만족하는 c를 구하는 문제입니다.

b = 15 , c = 19입니다.

 

먼저 덧셈역원 b는 구하기가 매우 쉽습니다. 단순히 n에서 a를 빼주면 바로 그게 덧셈역원 입니다.

 

이제 곱역원(c)를 구하는게 관건인데

11c mod 26 = 1 을 다시쓰면 11c ≡ 1 (mod 26) 로 다시쓸 수 있습니다.

이는 이번 겨울 신촌 icpc 1회차에서 들었던 합동 의 특징입니다.

따라서 11c + 26y = 1 로 다시 쓸 수 있습니다.

먼저 곱셈의 역원이 있는지 파악하기 위해서는 11(a)와 26(n)이 서로소 관계인지 파악해야 합니다.

따라서 gcd(11, 26) 이 1이 아니면 곱셈의 역원이 없는 것이므로 -1을 출력하고 

1이면 확장 유클리드 알고리즘을 활용해 c를 구해주면 됩니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
ll gcd(ll x, ll y);
ll ex_gcd(ll a, ll b, ll& x, ll& y);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    ll n, a, b, c;
    ll ggc;
    cin >> n >> a;
 
    b = n - a;
    cout << b<<' ';
 
    if (gcd(n, a) != 1) 
        cout << -1;
    else {
        ex_gcd(a, n, c, ggc);
        cout << c;
    }
 
    return 0;
}
ll gcd(ll x, ll y) {
    if (!y)return x;
    return gcd(y, x % y);
}
ll ex_gcd(ll a, ll b, ll& x, ll& y) { //gcd(a, b)를 return 
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll ret = ex_gcd(b, a % b, x, y);
    ll temp = y;
    y = x - (a / b) * y;
    x = temp;
    if (x <= 0) { //x를 양수로 만들어주는 작업 또는 오버플로우 방지
        x += b;
        y -= a;
    }
    return ret;
}