solution

Bối cảnh

Trong trao đổi khóa Diffie-Hellman, tính an toàn phụ thuộc vào cấp (order) của phần tử sinh $a$ trong nhóm nhân $\mathbb{Z}_p^*$ ($p$ nguyên tố): đó là số nguyên dương nhỏ nhất $k$ sao cho

$a^k \equiv 1 \pmod p.$

Cấp của $a$ luôn là ước của $p-1$ (định lý Lagrange / hệ quả của định lý Fermat nhỏ). Nếu cấp của $a$ đúng bằng $p-1$ thì $a$ là một căn nguyên thủy (primitive root) modulo $p$, thường dùng làm phần tử sinh công khai $g$ trong Diffie-Hellman/ElGamal.

Đề bài

Cho số nguyên tố $p$ và số nguyên $a$ với $1 \le a \le p-1$. Hãy tính cấp của $a$ trong $\mathbb{Z}_p^*$, tức số nguyên dương nhỏ nhất $k$ sao cho $a^k \equiv 1 \pmod p$.

Ràng buộc

• $3 \le p \le 10^6$, $p$ là số nguyên tố (đề bài đảm bảo).
• $1 \le a \le p - 1$.

Ví dụ

Input:

7 3

Output:

6

Giải thích: $3^1=3,\ 3^2=2,\ 3^3=6,\ 3^4=4,\ 3^5=5,\ 3^6=1 \pmod 7$. Vậy cấp của $3$ modulo $7$ là $6$ (và $3$ là một căn nguyên thủy modulo $7$).