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

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

14565번: 역원(Inverse) 구하기

---

Solved By: EEA(Extended Euclidean Algorithm), MMI(Modular Multiplicative Inverse)

 

(곱셈역에 대한 풀이만 하겠습니다.)

확장 유클리드 알고리즘과 모듈러 연산 곱셈 역원에 대해 배우기 좋은 문제였습니다.

(a * c) = 1(mod n)이라는 식에서 a가 주어지면 c를 구해야 합니다.

다음 식은 a * c = 1 + n * y로 정리할 수 있고, 이는 a * c - n * y = 1 꼴로 나타내어 Diophantine Equation의 형태로 나타낼 수 있습니다.

 

a와 n의 gcd는 주어진 식에 따라 1을 나타내야 하기에 1이 아니라면 곱셈역은 존재하지 않는 걸로 하고, -1을 출력하게 해주었습니다.

그리고, 확장 유클리드 알고리즘에서는 r1의 값이 0이 되었을 때, s0값이 c의 값을 나타내기 때문에 이를 알고 c를 리턴하게 해주었습니다.

c는 Zn이라는 0부터 n - 1까지의 정수 집합에 속하며 음수 값이 나온다면 Modular 연산의 특징을 이용하여 리턴하게 해주었습니다.

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

ll N, A;

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

ll exGCD(ll a, ll b){
    ll r0 = a, r1 = b, s0 = 1, s1 = 0, t0 = 0, t1 = 1;
    ll q, r, s, t;
    
    while(true){
        ll q = r0 / r1; // int로 선언했어서 시간 초과 난 거임
        
        r = r0 - q * r1;
        r0 = r1;
        r1 = r;
        
        s = s0 - q * s1;
        s0 = s1;
        s1 = s;
        
        t = t0 - q * t1;
        t0 = t1;
        t1 = t;
        
        if(r1 == 0) break;
    }
    
    return (s0 % b + b) % b;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> N >> A;
    
    cout << N - A << ' ';
    
    if(gcd(A, N) != 1){
        cout << -1;
        return 0;
    }
    cout << exGCD(A, N);
    
    return 0;
}