(14565) 역원(Inverse) 구하기

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

단계별로 풀어보기

45단계(수학 2) 2번째

 

 

 

덧셈역은 n-a라는 것을 아주 쉽게 알 수 있다.

ax+my=1에서 ax ≡ 1-my ≡ 1 (mod m)이므로 확장 유클리드 알고리즘으로 구한 x값이 a의 곱셈역이다.

a와 m이 서로소가 아니라면 역원은 없고, 구한 x값이 음수일수도 있으므로 Zn 내 범위로 변경해준다.

 

 

 

#include <iostream>
using namespace std;

int main() {
  long n, a;
  
  cin >> n >> a;
  
  cout << n-a << " ";
  
  long q;
  pair<long, long> r= {a, n};
  pair<long, long> s= {1, 0};
  pair<long, long> t= {0, 1};
  
  while(r.second){
    q= r.first/r.second;
    r= {r.second, r.first-r.second*q};
    s= {s.second, s.first-s.second*q};
    t= {t.second, t.first-t.second*q};
  }
  
  if(abs(r.first)!=1)  cout << -1;
  else  cout << (s.first>0 ? s.first : s.first+n);
  
  return 0;
}