RSA 키 만들기

시간 제한: 2000 ms메모리 제한: 256 MBSilver V

3

작성자: 관리자

문제

서로 다른 두 소수 $p$ , $q$ 와 정수 $e$ 를 받는다. $n = pq$ , $\varphi = (p-1)(q-1)$ 을 계산한다. $1 < e < \varphi$ 이고 $e$ 와 $\varphi$ 가 서로소이면 첫째 줄에 $n$ 과 $\varphi$ 를, 둘째 줄에 $ed \bmod \varphi = 1$ 을 만족하는 가장 작은 양의 정수 $d$ 를 출력한다. 조건을 만족하지 않으면 INVALID만 출력한다.

서로소 판정은 유클리드 호제법으로 한다. $d$ 는 1부터 차례로 검사해도 제한 안에 찾을 수 있다. 곱 $e \times d$ 가 int 범위를 넘을 수 있으므로 long long으로 계산한다.

입력

첫째 줄에 정수 $p$ , $q$ , $e$ 가 공백으로 구분되어 주어진다.

출력

첫째 줄에 $n$ 과 $\varphi$ 를 공백으로 구분해 출력하고 둘째 줄에 $d$ 를 출력한다. 조건을 만족하지 않으면 INVALID를 한 줄에 출력한다.

제한

$3 \le p, q \le 997$ 이고 $p \ne q$ 이며 둘 다 소수이다. $1 \le e \le 10^6$

문제 통계

4

전체 제출

2

정답

50%

정답률

2

정답자 수

1 \leq e \leq 1 0^{6}

입출력 예시

입력

5 11 3

출력

55 40
27

입력

11 3 10

출력

INVALID