Bài tập | NEU OJ

Nghịch đảo modulo là phép toán cốt lõi khi cài đặt RSA (tính khóa bí mật $d = e^{-1} \bmod \varphi(n)$ ) hay các sơ đồ chữ ký số.

Cho hai số nguyên $a, n$ . Hãy tìm số nguyên $x$ với $0 \le x < n$ sao cho $a \cdot x \equiv 1 \pmod n$ (nghịch đảo modulo của $a$ theo $n$ ).

Nếu nghịch đảo không tồn tại (tức $\gcd(a, n) \ne 1$ ), in ra $-1$ . Quy ước riêng: nếu $n = 1$ , in ra $0$ .

Định dạng đầu vào:
Một dòng duy nhất chứa hai số nguyên $a, n$ cách nhau bởi khoảng trắng ( $0 \le a < 10^{18}$ , $1 \le n < 2 \times 10^{18}$ ).
Định dạng đầu ra:
Một số nguyên duy nhất: nghịch đảo modulo của $a$ theo $n$ , hoặc $-1$ nếu không tồn tại.

solution