| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 592 | 380 | 297 | 68.119% |
문제
집합 Zn을 0부터 n-1까지의 정수 집합이라고 하자. Zn ∋ a, b, c 일 때, (a+b) mod n = 0이면 b는 a의 덧셈역이라고 하고 (a*c) mod n = 1이면 c는 a의 곱셈역이라고 한다.
정수 N, A가 주어졌을 때 Zn에서의 A의 덧셈역과 곱셈역을 구하시오.
단, 곱셈역을 구할 수 없으면 -1을 출력한다.
입력
첫 번째 줄에 N(2 ≤ N ≤ 1012)과 A(1 ≤ A < N)이 주어진다.
출력
첫 번째 줄에 A의 N에 대한 덧셈역과 곱셈역을 한 줄에 공백으로 구분하여 출력한다.
접근
덧셈의 역원은 당연히 N - A가 나온다.
곱셈의 역원이 문제인데, 처음에 종이에 식을 여러개 적어봤는데 쉽게 도출되지가 않았다.
알고리즘의 분류가 확장 유클리드 호제법이길래, 한번 검색해보았다. 링크
ax + by = c 인 식에서 x와 y를 구할 수 있는 방법이었다.
여기서는, Ax + Ny = 1 인 x 값을 도출해내면 됐다.
풀이
c = 1이 나오기 위해서는, A와 N의 최대공약수가 1이어야 한다. (서로소)
그 경우만 처리해주면 확장 유클리드 호제법으로 x의 값을 구해주면 된다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
ll N, A;
ll exEuclid(ll a, ll b, ll & x, ll & y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
ll gcd = exEuclid(b, a % b, x, y);
ll temp = y;
y = x - (a / b) * y;
x = temp;
if (x <= 0)
{
x += b;
y -= a;
}
return gcd;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
CIN2(N, A);
COUT2(N - A, "");
ll x, y;
exEuclid(A, N, x, y) == 1 ? COUT(x) : COUT(-1);
return 0;
}
Beginner